src/test/test_scheduler.c

   1 /* Copyright (c) 2014-2017, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 #include "orconfig.h"
   5
   6 #include <math.h>
   7
   8 #define SCHEDULER_KIST_PRIVATE
   9 #define TOR_CHANNEL_INTERNAL_
  10 #define CHANNEL_PRIVATE_
  11 #include "or.h"
  12 #include "config.h"
  13 #include "compat_libevent.h"
  14 #include "channel.h"
  15 #include "channeltls.h"
  16 #include "connection.h"
  17 #include "networkstatus.h"
  18 #define SCHEDULER_PRIVATE_
  19 #include "scheduler.h"
  20
  21 /* Test suite stuff */
  22 #include "test.h"
  23 #include "fakechans.h"
  24
  25 /* Shamelessly stolen from compat_libevent.c */
  26 #define V(major, minor, patch) \
  27   (((major) << 24) | ((minor) << 16) | ((patch) << 8))
  28
  29 /******************************************************************************
  30  * Statistical info
  31  *****************************************************************************/
  32 static int scheduler_compare_channels_mock_ctr = 0;
  33 static int scheduler_run_mock_ctr = 0;
  34
  35 /******************************************************************************
  36  * Utility functions and things we need to mock
  37  *****************************************************************************/
  38 static or_options_t mocked_options;
  39 static const or_options_t *
  40 mock_get_options(void)
  41 {
  42   return &mocked_options;
  43 }
  44
  45 static void
  46 cleanup_scheduler_options(void)
  47 {
  48   if (mocked_options.SchedulerTypes_) {
  49     SMARTLIST_FOREACH(mocked_options.SchedulerTypes_, int *, i, tor_free(i));
  50     smartlist_free(mocked_options.SchedulerTypes_);
  51     mocked_options.SchedulerTypes_ = NULL;
  52   }
  53 }
  54
  55 static void
  56 set_scheduler_options(int val)
  57 {
  58   int *type;
  59
  60   if (mocked_options.SchedulerTypes_ == NULL) {
  61     mocked_options.SchedulerTypes_ = smartlist_new();
  62   }
  63   type = tor_malloc_zero(sizeof(int));
  64   *type = val;
  65   smartlist_add(mocked_options.SchedulerTypes_, type);
  66 }
  67
  68 static void
  69 clear_options(void)
  70 {
  71   cleanup_scheduler_options();
  72   memset(&mocked_options, 0, sizeof(mocked_options));
  73 }
  74
  75 static int32_t
  76 mock_vanilla_networkstatus_get_param(
  77     const networkstatus_t *ns, const char *param_name, int32_t default_val,
  78     int32_t min_val, int32_t max_val)
  79 {
  80   (void)ns;
  81   (void)default_val;
  82   (void)min_val;
  83   (void)max_val;
  84   // only support KISTSchedRunInterval right now
  85   tor_assert(strcmp(param_name, "KISTSchedRunInterval")==0);
  86   return 0;
  87 }
  88
  89 static int32_t
  90 mock_kist_networkstatus_get_param(
  91     const networkstatus_t *ns, const char *param_name, int32_t default_val,
  92     int32_t min_val, int32_t max_val)
  93 {
  94   (void)ns;
  95   (void)default_val;
  96   (void)min_val;
  97   (void)max_val;
  98   // only support KISTSchedRunInterval right now
  99   tor_assert(strcmp(param_name, "KISTSchedRunInterval")==0);
 100   return 12;
 101 }
 102
 103 static int
 104 scheduler_compare_channels_mock(const void *c1_v,
 105                                 const void *c2_v)
 106 {
 107   uintptr_t p1, p2;
 108
 109   p1 = (uintptr_t)(c1_v);
 110   p2 = (uintptr_t)(c2_v);
 111
 112   ++scheduler_compare_channels_mock_ctr;
 113
 114   if (p1 == p2) return 0;
 115   else if (p1 < p2) return 1;
 116   else return -1;
 117 }
 118
 119 static void
 120 scheduler_run_noop_mock(void)
 121 {
 122   ++scheduler_run_mock_ctr;
 123 }
 124
 125 static circuitmux_t *mock_ccm_tgt_1 = NULL;
 126 static circuitmux_t *mock_ccm_tgt_2 = NULL;
 127 static circuitmux_t *mock_cgp_tgt_1 = NULL;
 128 static circuitmux_policy_t *mock_cgp_val_1 = NULL;
 129 static circuitmux_t *mock_cgp_tgt_2 = NULL;
 130 static circuitmux_policy_t *mock_cgp_val_2 = NULL;
 131
 132 static const circuitmux_policy_t *
 133 circuitmux_get_policy_mock(circuitmux_t *cmux)
 134 {
 135   const circuitmux_policy_t *result = NULL;
 136
 137   tt_assert(cmux != NULL);
 138   if (cmux) {
 139     if (cmux == mock_cgp_tgt_1) result = mock_cgp_val_1;
 140     else if (cmux == mock_cgp_tgt_2) result = mock_cgp_val_2;
 141     else result = circuitmux_get_policy__real(cmux);
 142   }
 143
 144  done:
 145   return result;
 146 }
 147
 148 static int
 149 circuitmux_compare_muxes_mock(circuitmux_t *cmux_1,
 150                               circuitmux_t *cmux_2)
 151 {
 152   int result = 0;
 153
 154   tt_assert(cmux_1 != NULL);
 155   tt_assert(cmux_2 != NULL);
 156
 157   if (cmux_1 != cmux_2) {
 158     if (cmux_1 == mock_ccm_tgt_1 && cmux_2 == mock_ccm_tgt_2) result = -1;
 159     else if (cmux_1 == mock_ccm_tgt_2 && cmux_2 == mock_ccm_tgt_1) {
 160       result = 1;
 161     } else {
 162       if (cmux_1 == mock_ccm_tgt_1 || cmux_1 == mock_ccm_tgt_2) result = -1;
 163       else if (cmux_2 == mock_ccm_tgt_1 || cmux_2 == mock_ccm_tgt_2) {
 164         result = 1;
 165       } else {
 166         result = circuitmux_compare_muxes__real(cmux_1, cmux_2);
 167       }
 168     }
 169   }
 170   /* else result = 0 always */
 171
 172  done:
 173   return result;
 174 }
 175
 176 typedef struct {
 177   const channel_t *chan;
 178   ssize_t cells;
 179 } flush_mock_channel_t;
 180
 181 static smartlist_t *chans_for_flush_mock = NULL;
 182
 183 static void
 184 channel_flush_some_cells_mock_free_all(void)
 185 {
 186   if (chans_for_flush_mock) {
 187     SMARTLIST_FOREACH_BEGIN(chans_for_flush_mock,
 188                             flush_mock_channel_t *,
 189                             flush_mock_ch) {
 190       SMARTLIST_DEL_CURRENT(chans_for_flush_mock, flush_mock_ch);
 191       tor_free(flush_mock_ch);
 192     } SMARTLIST_FOREACH_END(flush_mock_ch);
 193
 194     smartlist_free(chans_for_flush_mock);
 195     chans_for_flush_mock = NULL;
 196   }
 197 }
 198
 199 static void
 200 channel_flush_some_cells_mock_set(channel_t *chan, ssize_t num_cells)
 201 {
 202   int found = 0;
 203
 204   if (!chan) return;
 205   if (num_cells <= 0) return;
 206
 207   if (!chans_for_flush_mock) {
 208     chans_for_flush_mock = smartlist_new();
 209   }
 210
 211   SMARTLIST_FOREACH_BEGIN(chans_for_flush_mock,
 212                           flush_mock_channel_t *,
 213                           flush_mock_ch) {
 214     if (flush_mock_ch != NULL && flush_mock_ch->chan != NULL) {
 215       if (flush_mock_ch->chan == chan) {
 216         /* Found it */
 217         flush_mock_ch->cells = num_cells;
 218         found = 1;
 219         break;
 220       }
 221     } else {
 222       /* That shouldn't be there... */
 223       SMARTLIST_DEL_CURRENT(chans_for_flush_mock, flush_mock_ch);
 224       tor_free(flush_mock_ch);
 225     }
 226   } SMARTLIST_FOREACH_END(flush_mock_ch);
 227
 228   if (! found) {
 229     /* The loop didn't find it */
 230     flush_mock_channel_t *flush_mock_ch;
 231     flush_mock_ch = tor_malloc_zero(sizeof(*flush_mock_ch));
 232     flush_mock_ch->chan = chan;
 233     flush_mock_ch->cells = num_cells;
 234     smartlist_add(chans_for_flush_mock, flush_mock_ch);
 235   }
 236 }
 237
 238 static int
 239 channel_more_to_flush_mock(channel_t *chan)
 240 {
 241   tor_assert(chan);
 242
 243   flush_mock_channel_t *found_mock_ch = NULL;
 244
 245   SMARTLIST_FOREACH_BEGIN(chans_for_flush_mock,
 246                           flush_mock_channel_t *,
 247                           flush_mock_ch) {
 248     if (flush_mock_ch != NULL && flush_mock_ch->chan != NULL) {
 249       if (flush_mock_ch->chan == chan) {
 250         /* Found it */
 251         found_mock_ch = flush_mock_ch;
 252         break;
 253       }
 254     } else {
 255       /* That shouldn't be there... */
 256       SMARTLIST_DEL_CURRENT(chans_for_flush_mock, flush_mock_ch);
 257       tor_free(flush_mock_ch);
 258     }
 259   } SMARTLIST_FOREACH_END(flush_mock_ch);
 260
 261   tor_assert(found_mock_ch);
 262
 263   /* Check if any circuits would like to queue some */
 264   /* special for the mock: return the number of cells (instead of 1), or zero
 265    * if nothing to flush */
 266   return (found_mock_ch->cells > 0 ? (int)found_mock_ch->cells : 0 );
 267 }
 268
 269 static void
 270 channel_write_to_kernel_mock(channel_t *chan)
 271 {
 272   (void)chan;
 273   //log_debug(LD_SCHED, "chan=%d writing to kernel",
 274   //    (int)chan->global_identifier);
 275 }
 276
 277 static int
 278 channel_should_write_to_kernel_mock(outbuf_table_t *ot, channel_t *chan)
 279 {
 280   (void)ot;
 281   (void)chan;
 282   return 1;
 283   /* We could make this more complicated if we wanted. But I don't think doing
 284    * so tests much of anything */
 285   //static int called_counter = 0;
 286   //if (++called_counter >= 3) {
 287   //  called_counter -= 3;
 288   //  log_debug(LD_SCHED, "chan=%d should write to kernel",
 289   //      (int)chan->global_identifier);
 290   //  return 1;
 291   //}
 292   //return 0;
 293 }
 294
 295 static ssize_t
 296 channel_flush_some_cells_mock(channel_t *chan, ssize_t num_cells)
 297 {
 298   ssize_t flushed = 0, max;
 299   char unlimited = 0;
 300   flush_mock_channel_t *found = NULL;
 301
 302   tt_ptr_op(chan, OP_NE, NULL);
 303   if (chan) {
 304     if (num_cells < 0) {
 305       num_cells = 0;
 306       unlimited = 1;
 307     }
 308
 309     /* Check if we have it */
 310     if (chans_for_flush_mock != NULL) {
 311       SMARTLIST_FOREACH_BEGIN(chans_for_flush_mock,
 312                               flush_mock_channel_t *,
 313                               flush_mock_ch) {
 314         if (flush_mock_ch != NULL && flush_mock_ch->chan != NULL) {
 315           if (flush_mock_ch->chan == chan) {
 316             /* Found it */
 317             found = flush_mock_ch;
 318             break;
 319           }
 320         } else {
 321           /* That shouldn't be there... */
 322           SMARTLIST_DEL_CURRENT(chans_for_flush_mock, flush_mock_ch);
 323           tor_free(flush_mock_ch);
 324         }
 325       } SMARTLIST_FOREACH_END(flush_mock_ch);
 326
 327       if (found) {
 328         /* We found one */
 329         if (found->cells < 0) found->cells = 0;
 330
 331         if (unlimited) max = found->cells;
 332         else max = MIN(found->cells, num_cells);
 333
 334         flushed += max;
 335         found->cells -= max;
 336       }
 337     }
 338   }
 339
 340  done:
 341   return flushed;
 342 }
 343
 344 static void
 345 update_socket_info_impl_mock(socket_table_ent_t *ent)
 346 {
 347   ent->cwnd = ent->unacked = ent->mss = ent->notsent = 0;
 348   ent->limit = INT_MAX;
 349 }
 350
 351 static void
 352 perform_channel_state_tests(int KISTSchedRunInterval, int sched_type)
 353 {
 354   channel_t *ch1 = NULL, *ch2 = NULL;
 355   int old_count;
 356
 357   /* setup options so we're sure about what sched we are running */
 358   MOCK(get_options, mock_get_options);
 359   clear_options();
 360   mocked_options.KISTSchedRunInterval = KISTSchedRunInterval;
 361   set_scheduler_options(sched_type);
 362
 363   /* Set up scheduler */
 364   scheduler_init();
 365   /*
 366    * Install the compare channels mock so we can test
 367    * scheduler_touch_channel().
 368    */
 369   MOCK(scheduler_compare_channels, scheduler_compare_channels_mock);
 370   /*
 371    * Disable scheduler_run so we can just check the state transitions
 372    * without having to make everything it might call work too.
 373    */
 374   ((scheduler_t *) the_scheduler)->run = scheduler_run_noop_mock;
 375
 376   tt_int_op(smartlist_len(channels_pending), OP_EQ, 0);
 377
 378   /* Set up a fake channel */
 379   ch1 = new_fake_channel();
 380   tt_assert(ch1);
 381
 382   /* Start it off in OPENING */
 383   ch1->state = CHANNEL_STATE_OPENING;
 384   /* Try to register it */
 385   channel_register(ch1);
 386   tt_assert(ch1->registered);
 387
 388   /* It should start off in SCHED_CHAN_IDLE */
 389   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 390
 391   /* Now get another one */
 392   ch2 = new_fake_channel();
 393   tt_assert(ch2);
 394   ch2->state = CHANNEL_STATE_OPENING;
 395   channel_register(ch2);
 396   tt_assert(ch2->registered);
 397
 398   /* Send ch1 to SCHED_CHAN_WAITING_TO_WRITE */
 399   scheduler_channel_has_waiting_cells(ch1);
 400   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_TO_WRITE);
 401
 402   /* This should send it to SCHED_CHAN_PENDING */
 403   scheduler_channel_wants_writes(ch1);
 404   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 405   tt_int_op(smartlist_len(channels_pending), OP_EQ, 1);
 406
 407   /* Now send ch2 to SCHED_CHAN_WAITING_FOR_CELLS */
 408   scheduler_channel_wants_writes(ch2);
 409   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 410
 411   /* Drop ch2 back to idle */
 412   scheduler_channel_doesnt_want_writes(ch2);
 413   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 414
 415   /* ...and back to SCHED_CHAN_WAITING_FOR_CELLS */
 416   scheduler_channel_wants_writes(ch2);
 417   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 418
 419   /* ...and this should kick ch2 into SCHED_CHAN_PENDING */
 420   scheduler_channel_has_waiting_cells(ch2);
 421   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 422   tt_int_op(smartlist_len(channels_pending), OP_EQ, 2);
 423
 424   /* This should send ch2 to SCHED_CHAN_WAITING_TO_WRITE */
 425   scheduler_channel_doesnt_want_writes(ch2);
 426   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_TO_WRITE);
 427   tt_int_op(smartlist_len(channels_pending), OP_EQ, 1);
 428
 429   /* ...and back to SCHED_CHAN_PENDING */
 430   scheduler_channel_wants_writes(ch2);
 431   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 432   tt_int_op(smartlist_len(channels_pending), OP_EQ, 2);
 433
 434   /* Now we exercise scheduler_touch_channel */
 435   old_count = scheduler_compare_channels_mock_ctr;
 436   scheduler_touch_channel(ch1);
 437   tt_assert(scheduler_compare_channels_mock_ctr > old_count);
 438
 439   /* Release the ch2 and then do it another time to make sure it doesn't blow
 440    * up and we are still in a quiescent state. */
 441   scheduler_release_channel(ch2);
 442   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 443   tt_int_op(smartlist_len(channels_pending), OP_EQ, 1);
 444   /* Cheat a bit so make the release more confused but also will tells us if
 445    * the release did put the channel in the right state. */
 446   ch2->scheduler_state = SCHED_CHAN_PENDING;
 447   scheduler_release_channel(ch2);
 448   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 449   tt_int_op(smartlist_len(channels_pending), OP_EQ, 1);
 450
 451   /* Close */
 452   channel_mark_for_close(ch1);
 453   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_CLOSING);
 454   channel_mark_for_close(ch2);
 455   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_CLOSING);
 456   channel_closed(ch1);
 457   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_CLOSED);
 458   ch1 = NULL;
 459   channel_closed(ch2);
 460   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_CLOSED);
 461   ch2 = NULL;
 462
 463   /* Shut things down */
 464
 465   channel_free_all();
 466   scheduler_free_all();
 467
 468  done:
 469   tor_free(ch1);
 470   tor_free(ch2);
 471
 472   UNMOCK(scheduler_compare_channels);
 473   UNMOCK(get_options);
 474   cleanup_scheduler_options();
 475
 476   return;
 477 }
 478
 479 static void
 480 test_scheduler_compare_channels(void *arg)
 481 {
 482   /* We don't actually need whole fake channels... */
 483   channel_t c1, c2;
 484   /* ...and some dummy circuitmuxes too */
 485   circuitmux_t *cm1 = NULL, *cm2 = NULL;
 486   int result;
 487
 488   (void)arg;
 489
 490   /* We can't actually see sizeof(circuitmux_t) from here */
 491   cm1 = tor_malloc_zero(sizeof(void *));
 492   cm2 = tor_malloc_zero(sizeof(void *));
 493
 494   c1.cmux = cm1;
 495   c2.cmux = cm2;
 496
 497   /* Configure circuitmux_get_policy() mock */
 498   mock_cgp_tgt_1 = cm1;
 499   mock_cgp_tgt_2 = cm2;
 500
 501   /*
 502    * This is to test the different-policies case, which uses the policy
 503    * cast to an uintptr_t as an arbitrary but definite thing to compare.
 504    */
 505   mock_cgp_val_1 = tor_malloc_zero(16);
 506   mock_cgp_val_2 = tor_malloc_zero(16);
 507   if ( ((uintptr_t) mock_cgp_val_1) > ((uintptr_t) mock_cgp_val_2) ) {
 508     void *tmp = mock_cgp_val_1;
 509     mock_cgp_val_1 = mock_cgp_val_2;
 510     mock_cgp_val_2 = tmp;
 511   }
 512
 513   MOCK(circuitmux_get_policy, circuitmux_get_policy_mock);
 514
 515   /* Now set up circuitmux_compare_muxes() mock using cm1/cm2 */
 516   mock_ccm_tgt_1 = cm1;
 517   mock_ccm_tgt_2 = cm2;
 518   MOCK(circuitmux_compare_muxes, circuitmux_compare_muxes_mock);
 519
 520   /* Equal-channel case */
 521   result = scheduler_compare_channels(&c1, &c1);
 522   tt_int_op(result, OP_EQ, 0);
 523
 524   /* Distinct channels, distinct policies */
 525   result = scheduler_compare_channels(&c1, &c2);
 526   tt_int_op(result, OP_EQ, -1);
 527   result = scheduler_compare_channels(&c2, &c1);
 528   tt_int_op(result, OP_EQ, 1);
 529
 530   /* Distinct channels, same policy */
 531   tor_free(mock_cgp_val_2);
 532   mock_cgp_val_2 = mock_cgp_val_1;
 533   result = scheduler_compare_channels(&c1, &c2);
 534   tt_int_op(result, OP_EQ, -1);
 535   result = scheduler_compare_channels(&c2, &c1);
 536   tt_int_op(result, OP_EQ, 1);
 537
 538  done:
 539
 540   UNMOCK(circuitmux_compare_muxes);
 541   mock_ccm_tgt_1 = NULL;
 542   mock_ccm_tgt_2 = NULL;
 543
 544   UNMOCK(circuitmux_get_policy);
 545   mock_cgp_tgt_1 = NULL;
 546   mock_cgp_tgt_2 = NULL;
 547
 548   tor_free(cm1);
 549   tor_free(cm2);
 550
 551   if (mock_cgp_val_1 != mock_cgp_val_2)
 552     tor_free(mock_cgp_val_1);
 553   tor_free(mock_cgp_val_2);
 554   mock_cgp_val_1 = NULL;
 555   mock_cgp_val_2 = NULL;
 556
 557   return;
 558 }
 559
 560 /******************************************************************************
 561  * The actual tests!
 562  *****************************************************************************/
 563
 564 static void
 565 test_scheduler_loop_vanilla(void *arg)
 566 {
 567   (void)arg;
 568   channel_t *ch1 = NULL, *ch2 = NULL;
 569   void (*run_func_ptr)(void);
 570
 571   /* setup options so we're sure about what sched we are running */
 572   MOCK(get_options, mock_get_options);
 573   clear_options();
 574   set_scheduler_options(SCHEDULER_VANILLA);
 575   mocked_options.KISTSchedRunInterval = 0;
 576
 577   /* Set up scheduler */
 578   scheduler_init();
 579   /*
 580    * Install the compare channels mock so we can test
 581    * scheduler_touch_channel().
 582    */
 583   MOCK(scheduler_compare_channels, scheduler_compare_channels_mock);
 584   /*
 585    * Disable scheduler_run so we can just check the state transitions
 586    * without having to make everything it might call work too.
 587    */
 588   run_func_ptr = the_scheduler->run;
 589   ((scheduler_t *) the_scheduler)->run = scheduler_run_noop_mock;
 590
 591   tt_int_op(smartlist_len(channels_pending), OP_EQ, 0);
 592
 593   /* Set up a fake channel */
 594   ch1 = new_fake_channel();
 595   ch1->magic = TLS_CHAN_MAGIC;
 596   tt_assert(ch1);
 597
 598   /* Start it off in OPENING */
 599   ch1->state = CHANNEL_STATE_OPENING;
 600   /* Try to register it */
 601   channel_register(ch1);
 602   tt_assert(ch1->registered);
 603   /* Finish opening it */
 604   channel_change_state_open(ch1);
 605
 606   /* It should start off in SCHED_CHAN_IDLE */
 607   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 608
 609   /* Now get another one */
 610   ch2 = new_fake_channel();
 611   ch2->magic = TLS_CHAN_MAGIC;
 612   tt_assert(ch2);
 613   ch2->state = CHANNEL_STATE_OPENING;
 614   channel_register(ch2);
 615   tt_assert(ch2->registered);
 616   /*
 617    * Don't open ch2; then channel_num_cells_writeable() will return
 618    * zero and we'll get coverage of that exception case in scheduler_run()
 619    */
 620
 621   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_OPEN);
 622   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_OPENING);
 623
 624   /* Send it to SCHED_CHAN_WAITING_TO_WRITE */
 625   scheduler_channel_has_waiting_cells(ch1);
 626   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_TO_WRITE);
 627
 628   /* This should send it to SCHED_CHAN_PENDING */
 629   scheduler_channel_wants_writes(ch1);
 630   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 631   tt_int_op(smartlist_len(channels_pending), OP_EQ, 1);
 632
 633   /* Now send ch2 to SCHED_CHAN_WAITING_FOR_CELLS */
 634   scheduler_channel_wants_writes(ch2);
 635   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 636
 637   /* Drop ch2 back to idle */
 638   scheduler_channel_doesnt_want_writes(ch2);
 639   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 640
 641   /* ...and back to SCHED_CHAN_WAITING_FOR_CELLS */
 642   scheduler_channel_wants_writes(ch2);
 643   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 644
 645   /* ...and this should kick ch2 into SCHED_CHAN_PENDING */
 646   scheduler_channel_has_waiting_cells(ch2);
 647   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 648   tt_int_op(smartlist_len(channels_pending), OP_EQ, 2);
 649
 650   /*
 651    * Now we've got two pending channels and need to fire off
 652    * the scheduler run() that we kept.
 653    */
 654   run_func_ptr();
 655
 656   /*
 657    * Assert that they're still in the states we left and aren't still
 658    * pending
 659    */
 660   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_OPEN);
 661   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_OPENING);
 662   tt_assert(ch1->scheduler_state != SCHED_CHAN_PENDING);
 663   tt_assert(ch2->scheduler_state != SCHED_CHAN_PENDING);
 664   tt_int_op(smartlist_len(channels_pending), OP_EQ, 0);
 665
 666   /* Now, finish opening ch2, and get both back to pending */
 667   channel_change_state_open(ch2);
 668   scheduler_channel_wants_writes(ch1);
 669   scheduler_channel_wants_writes(ch2);
 670   scheduler_channel_has_waiting_cells(ch1);
 671   scheduler_channel_has_waiting_cells(ch2);
 672   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_OPEN);
 673   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_OPEN);
 674   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 675   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 676   tt_int_op(smartlist_len(channels_pending), OP_EQ, 2);
 677
 678   /* Now, set up the channel_flush_some_cells() mock */
 679   MOCK(channel_flush_some_cells, channel_flush_some_cells_mock);
 680   /*
 681    * 16 cells on ch1 means it'll completely drain into the 32 cells
 682    * fakechan's num_cells_writeable() returns.
 683    */
 684   channel_flush_some_cells_mock_set(ch1, 16);
 685   /*
 686    * This one should get sent back to pending, since num_cells_writeable()
 687    * will still return non-zero.
 688    */
 689   channel_flush_some_cells_mock_set(ch2, 48);
 690
 691   /*
 692    * And re-run the scheduler run() loop with non-zero returns from
 693    * channel_flush_some_cells() this time.
 694    */
 695   run_func_ptr();
 696
 697   /*
 698    * ch1 should have gone to SCHED_CHAN_WAITING_FOR_CELLS, with 16 flushed
 699    * and 32 writeable.
 700    */
 701   tt_int_op(ch1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 702   /*
 703    * ...ch2 should also have gone to SCHED_CHAN_WAITING_FOR_CELLS, with
 704    * channel_more_to_flush() returning false and channel_num_cells_writeable()
 705    * > 0/
 706    */
 707   tt_int_op(ch2->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
 708
 709   /* Close */
 710   channel_mark_for_close(ch1);
 711   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_CLOSING);
 712   channel_mark_for_close(ch2);
 713   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_CLOSING);
 714   channel_closed(ch1);
 715   tt_int_op(ch1->state, OP_EQ, CHANNEL_STATE_CLOSED);
 716   ch1 = NULL;
 717   channel_closed(ch2);
 718   tt_int_op(ch2->state, OP_EQ, CHANNEL_STATE_CLOSED);
 719   ch2 = NULL;
 720
 721   /* Shut things down */
 722   channel_flush_some_cells_mock_free_all();
 723   channel_free_all();
 724   scheduler_free_all();
 725
 726  done:
 727   tor_free(ch1);
 728   tor_free(ch2);
 729   cleanup_scheduler_options();
 730
 731   UNMOCK(channel_flush_some_cells);
 732   UNMOCK(scheduler_compare_channels);
 733   UNMOCK(get_options);
 734 }
 735
 736 static void
 737 test_scheduler_loop_kist(void *arg)
 738 {
 739   (void) arg;
 740
 741 #ifndef HAVE_KIST_SUPPORT
 742   return;
 743 #endif
 744
 745   channel_t *ch1 = new_fake_channel(), *ch2 = new_fake_channel();
 746   channel_t *ch3 = new_fake_channel();
 747
 748   /* setup options so we're sure about what sched we are running */
 749   MOCK(get_options, mock_get_options);
 750   MOCK(channel_flush_some_cells, channel_flush_some_cells_mock);
 751   MOCK(channel_more_to_flush, channel_more_to_flush_mock);
 752   MOCK(channel_write_to_kernel, channel_write_to_kernel_mock);
 753   MOCK(channel_should_write_to_kernel, channel_should_write_to_kernel_mock);
 754   MOCK(update_socket_info_impl, update_socket_info_impl_mock);
 755   clear_options();
 756   mocked_options.KISTSchedRunInterval = 11;
 757   set_scheduler_options(SCHEDULER_KIST);
 758   scheduler_init();
 759
 760   tt_assert(ch1);
 761   ch1->magic = TLS_CHAN_MAGIC;
 762   ch1->state = CHANNEL_STATE_OPENING;
 763   channel_register(ch1);
 764   tt_assert(ch1->registered);
 765   channel_change_state_open(ch1);
 766   scheduler_channel_has_waiting_cells(ch1);
 767   scheduler_channel_wants_writes(ch1);
 768   channel_flush_some_cells_mock_set(ch1, 5);
 769
 770   tt_assert(ch2);
 771   ch2->magic = TLS_CHAN_MAGIC;
 772   ch2->state = CHANNEL_STATE_OPENING;
 773   channel_register(ch2);
 774   tt_assert(ch2->registered);
 775   channel_change_state_open(ch2);
 776   scheduler_channel_has_waiting_cells(ch2);
 777   scheduler_channel_wants_writes(ch2);
 778   channel_flush_some_cells_mock_set(ch2, 5);
 779
 780   the_scheduler->run();
 781
 782   scheduler_channel_has_waiting_cells(ch1);
 783   channel_flush_some_cells_mock_set(ch1, 5);
 784
 785   the_scheduler->run();
 786
 787   scheduler_channel_has_waiting_cells(ch1);
 788   channel_flush_some_cells_mock_set(ch1, 5);
 789   scheduler_channel_has_waiting_cells(ch2);
 790   channel_flush_some_cells_mock_set(ch2, 5);
 791
 792   the_scheduler->run();
 793
 794   channel_flush_some_cells_mock_free_all();
 795
 796   /* We'll try to run this closed channel threw the scheduler loop and make
 797    * sure it ends up in the right state. */
 798   tt_assert(ch3);
 799   ch3->magic = TLS_CHAN_MAGIC;
 800   ch3->state = CHANNEL_STATE_OPEN;
 801   circuitmux_free(ch3->cmux);
 802   ch3->cmux = circuitmux_alloc();
 803   channel_register(ch3);
 804   tt_assert(ch3->registered);
 805
 806   ch3->scheduler_state = SCHED_CHAN_WAITING_FOR_CELLS;
 807   scheduler_channel_has_waiting_cells(ch3);
 808   /* Should be in the pending list now waiting to be handled. */
 809   tt_int_op(ch3->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
 810   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
 811   /* By running the scheduler on a closed channel, it should end up in the
 812    * IDLE state and not in the pending channel list. */
 813   ch3->state = CHANNEL_STATE_CLOSED;
 814   the_scheduler->run();
 815   tt_int_op(ch3->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
 816   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
 817
 818  done:
 819   /* Prep the channel so the free() function doesn't explode. */
 820   ch1->state = ch2->state = ch3->state = CHANNEL_STATE_CLOSED;
 821   ch1->registered = ch2->registered = ch3->registered = 0;
 822   channel_free(ch1);
 823   channel_free(ch2);
 824   channel_free(ch3);
 825   UNMOCK(update_socket_info_impl);
 826   UNMOCK(channel_should_write_to_kernel);
 827   UNMOCK(channel_write_to_kernel);
 828   UNMOCK(channel_more_to_flush);
 829   UNMOCK(channel_flush_some_cells);
 830   UNMOCK(get_options);
 831   scheduler_free_all();
 832   return;
 833 }
 834
 835 static void
 836 test_scheduler_channel_states(void *arg)
 837 {
 838   (void)arg;
 839   perform_channel_state_tests(-1, SCHEDULER_VANILLA);
 840   perform_channel_state_tests(11, SCHEDULER_KIST_LITE);
 841 #ifdef HAVE_KIST_SUPPORT
 842   perform_channel_state_tests(11, SCHEDULER_KIST);
 843 #endif
 844 }
 845
 846 static void
 847 test_scheduler_initfree(void *arg)
 848 {
 849   (void)arg;
 850
 851   tt_ptr_op(channels_pending, ==, NULL);
 852   tt_ptr_op(run_sched_ev, ==, NULL);
 853
 854   MOCK(get_options, mock_get_options);
 855   set_scheduler_options(SCHEDULER_KIST);
 856   set_scheduler_options(SCHEDULER_KIST_LITE);
 857   set_scheduler_options(SCHEDULER_VANILLA);
 858
 859   scheduler_init();
 860
 861   tt_ptr_op(channels_pending, !=, NULL);
 862   tt_ptr_op(run_sched_ev, !=, NULL);
 863   /* We have specified nothing in the torrc and there's no consensus so the
 864    * KIST scheduler is what should be in use */
 865   tt_ptr_op(the_scheduler, ==, get_kist_scheduler());
 866   tt_int_op(sched_run_interval, ==, 10);
 867
 868   scheduler_free_all();
 869
 870   tt_ptr_op(channels_pending, ==, NULL);
 871   tt_ptr_op(run_sched_ev, ==, NULL);
 872
 873  done:
 874   UNMOCK(get_options);
 875   cleanup_scheduler_options();
 876   return;
 877 }
 878
 879 static void
 880 test_scheduler_can_use_kist(void *arg)
 881 {
 882   (void)arg;
 883
 884   int res_should, res_freq;
 885   MOCK(get_options, mock_get_options);
 886
 887   /* Test force enabling of KIST */
 888   clear_options();
 889   mocked_options.KISTSchedRunInterval = 1234;
 890   res_should = scheduler_can_use_kist();
 891   res_freq = kist_scheduler_run_interval();
 892 #ifdef HAVE_KIST_SUPPORT
 893   tt_int_op(res_should, ==, 1);
 894 #else /* HAVE_KIST_SUPPORT */
 895   tt_int_op(res_should, ==, 0);
 896 #endif /* HAVE_KIST_SUPPORT */
 897   tt_int_op(res_freq, ==, 1234);
 898
 899   /* Test defer to consensus, but no consensus available */
 900   clear_options();
 901   mocked_options.KISTSchedRunInterval = 0;
 902   res_should = scheduler_can_use_kist();
 903   res_freq = kist_scheduler_run_interval();
 904 #ifdef HAVE_KIST_SUPPORT
 905   tt_int_op(res_should, ==, 1);
 906 #else /* HAVE_KIST_SUPPORT */
 907   tt_int_op(res_should, ==, 0);
 908 #endif /* HAVE_KIST_SUPPORT */
 909   tt_int_op(res_freq, ==, 10);
 910
 911   /* Test defer to consensus, and kist consensus available */
 912   MOCK(networkstatus_get_param, mock_kist_networkstatus_get_param);
 913   clear_options();
 914   mocked_options.KISTSchedRunInterval = 0;
 915   res_should = scheduler_can_use_kist();
 916   res_freq = kist_scheduler_run_interval();
 917 #ifdef HAVE_KIST_SUPPORT
 918   tt_int_op(res_should, ==, 1);
 919 #else /* HAVE_KIST_SUPPORT */
 920   tt_int_op(res_should, ==, 0);
 921 #endif /* HAVE_KIST_SUPPORT */
 922   tt_int_op(res_freq, ==, 12);
 923   UNMOCK(networkstatus_get_param);
 924
 925   /* Test defer to consensus, and vanilla consensus available */
 926   MOCK(networkstatus_get_param, mock_vanilla_networkstatus_get_param);
 927   clear_options();
 928   mocked_options.KISTSchedRunInterval = 0;
 929   res_should = scheduler_can_use_kist();
 930   res_freq = kist_scheduler_run_interval();
 931   tt_int_op(res_should, ==, 0);
 932   tt_int_op(res_freq, ==, 0);
 933   UNMOCK(networkstatus_get_param);
 934
 935  done:
 936   UNMOCK(get_options);
 937   return;
 938 }
 939
 940 static void
 941 test_scheduler_ns_changed(void *arg)
 942 {
 943   (void) arg;
 944
 945   /*
 946    * Currently no scheduler implementations use the old/new consensuses passed
 947    * in scheduler_notify_networkstatus_changed, so it is okay to pass NULL.
 948    *
 949    * "But then what does test actually exercise???" It tests that
 950    * scheduler_notify_networkstatus_changed fetches the correct value from the
 951    * consensus, and then switches the scheduler if necessasry.
 952    */
 953
 954   MOCK(get_options, mock_get_options);
 955   clear_options();
 956   set_scheduler_options(SCHEDULER_KIST);
 957   set_scheduler_options(SCHEDULER_VANILLA);
 958
 959   tt_ptr_op(the_scheduler, ==, NULL);
 960
 961   /* Change from vanilla to kist via consensus */
 962   the_scheduler = get_vanilla_scheduler();
 963   MOCK(networkstatus_get_param, mock_kist_networkstatus_get_param);
 964   scheduler_notify_networkstatus_changed();
 965   UNMOCK(networkstatus_get_param);
 966 #ifdef HAVE_KIST_SUPPORT
 967   tt_ptr_op(the_scheduler, ==, get_kist_scheduler());
 968 #else
 969   tt_ptr_op(the_scheduler, ==, get_vanilla_scheduler());
 970 #endif
 971
 972   /* Change from kist to vanilla via consensus */
 973   the_scheduler = get_kist_scheduler();
 974   MOCK(networkstatus_get_param, mock_vanilla_networkstatus_get_param);
 975   scheduler_notify_networkstatus_changed();
 976   UNMOCK(networkstatus_get_param);
 977   tt_ptr_op(the_scheduler, ==, get_vanilla_scheduler());
 978
 979   /* Doesn't change when using KIST */
 980   the_scheduler = get_kist_scheduler();
 981   MOCK(networkstatus_get_param, mock_kist_networkstatus_get_param);
 982   scheduler_notify_networkstatus_changed();
 983   UNMOCK(networkstatus_get_param);
 984 #ifdef HAVE_KIST_SUPPORT
 985   tt_ptr_op(the_scheduler, ==, get_kist_scheduler());
 986 #else
 987   tt_ptr_op(the_scheduler, ==, get_vanilla_scheduler());
 988 #endif
 989
 990   /* Doesn't change when using vanilla */
 991   the_scheduler = get_vanilla_scheduler();
 992   MOCK(networkstatus_get_param, mock_vanilla_networkstatus_get_param);
 993   scheduler_notify_networkstatus_changed();
 994   UNMOCK(networkstatus_get_param);
 995   tt_ptr_op(the_scheduler, ==, get_vanilla_scheduler());
 996
 997  done:
 998   UNMOCK(get_options);
 999   cleanup_scheduler_options();
1000   return;
1001 }
1002
1003 /*
1004  * Mocked functions for the kist_pending_list test.
1005  */
1006
1007 static int mock_flush_some_cells_num = 1;
1008 static int mock_more_to_flush = 0;
1009 static int mock_update_socket_info_limit = 0;
1010
1011 static ssize_t
1012 channel_flush_some_cells_mock_var(channel_t *chan, ssize_t num_cells)
1013 {
1014   (void) chan;
1015   (void) num_cells;
1016   return mock_flush_some_cells_num;
1017 }
1018
1019 /* Because when we flush cells, it is possible that the connection outbuf gets
1020  * fully drained, the wants to write scheduler event is fired back while we
1021  * are in the scheduler loop so this mock function does it for us.
1022  * Furthermore, the socket limit is set to 0 so once this is triggered, it
1023  * informs the scheduler that it can't write on the socket anymore. */
1024 static void
1025 channel_write_to_kernel_mock_trigger_24700(channel_t *chan)
1026 {
1027   static int chan_id_seen[2] = {0};
1028   if (++chan_id_seen[chan->global_identifier - 1] > 1) {
1029     tt_assert(0);
1030   }
1031
1032   scheduler_channel_wants_writes(chan);
1033
1034  done:
1035   return;
1036 }
1037
1038 static int
1039 channel_more_to_flush_mock_var(channel_t *chan)
1040 {
1041   (void) chan;
1042   return mock_more_to_flush;
1043 }
1044
1045 static void
1046 update_socket_info_impl_mock_var(socket_table_ent_t *ent)
1047 {
1048   ent->cwnd = ent->unacked = ent->mss = ent->notsent = 0;
1049   ent->limit = mock_update_socket_info_limit;
1050 }
1051
1052 static void
1053 test_scheduler_kist_pending_list(void *arg)
1054 {
1055   (void) arg;
1056
1057 #ifndef HAVE_KIST_SUPPORT
1058   return;
1059 #endif
1060
1061   /* This is for testing the channel flow with the pending list that is
1062    * depending on the channel state, what will be the expected behavior of the
1063    * scheduler with that list.
1064    *
1065    * For instance, we want to catch double channel add or removing a channel
1066    * that doesn't exists, or putting a channel in the list in a wrong state.
1067    * Essentially, this will articifically test cases of the KIST main loop and
1068    * entry point in the channel subsystem.
1069    *
1070    * In part, this is to also catch things like #24700 and provide a test bed
1071    * for more testing in the future like so. */
1072
1073   /* Mocking a series of scheduler function to control the flow of the
1074    * scheduler loop to test every use cases and assess the pending list. */
1075   MOCK(get_options, mock_get_options);
1076   MOCK(channel_flush_some_cells, channel_flush_some_cells_mock_var);
1077   MOCK(channel_more_to_flush, channel_more_to_flush_mock_var);
1078   MOCK(update_socket_info_impl, update_socket_info_impl_mock_var);
1079   MOCK(channel_write_to_kernel, channel_write_to_kernel_mock);
1080   MOCK(channel_should_write_to_kernel, channel_should_write_to_kernel_mock);
1081
1082   /* Setup options so we're sure about what sched we are running */
1083   mocked_options.KISTSchedRunInterval = 10;
1084   set_scheduler_options(SCHEDULER_KIST);
1085
1086   /* Init scheduler. */
1087   scheduler_init();
1088
1089   /* Initialize a channel. We'll need a second channel for the #24700 bug
1090    * test. */
1091   channel_t *chan1 = new_fake_channel();
1092   channel_t *chan2 = new_fake_channel();
1093   tt_assert(chan1);
1094   tt_assert(chan2);
1095   chan1->magic = chan2->magic = TLS_CHAN_MAGIC;
1096   channel_register(chan1);
1097   channel_register(chan2);
1098   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
1099   tt_int_op(chan1->sched_heap_idx, OP_EQ, -1);
1100   tt_int_op(chan2->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
1101   tt_int_op(chan2->sched_heap_idx, OP_EQ, -1);
1102
1103   /* Once a channel becomes OPEN, it always have at least one cell in it so
1104    * the scheduler is notified that the channel wants to write so this is the
1105    * first step. Might not make sense to you but it is the way it is. */
1106   scheduler_channel_wants_writes(chan1);
1107   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
1108   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1109
1110   /* Signal the scheduler that it has waiting cells which means the channel
1111    * will get scheduled. */
1112   scheduler_channel_has_waiting_cells(chan1);
1113   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1114   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1115   /* Subsequent call should not add it more times. It is possible we add many
1116    * cells in rapid succession before the channel is scheduled. */
1117   scheduler_channel_has_waiting_cells(chan1);
1118   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1119   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1120   scheduler_channel_has_waiting_cells(chan1);
1121   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1122   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1123
1124   /* We'll flush one cell and make it that the socket can write but no more to
1125    * flush else we end up in an infinite loop. We expect the channel to be put
1126    * in waiting for cells state and the pending list empty. */
1127   mock_update_socket_info_limit = INT_MAX;
1128   mock_more_to_flush = 0;
1129   the_scheduler->run();
1130   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1131   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
1132
1133   /* Lets make believe that a cell is now in the channel but this time the
1134    * channel can't write so obviously it has more to flush. We expect the
1135    * channel to be back in the pending list. */
1136   scheduler_channel_has_waiting_cells(chan1);
1137   mock_update_socket_info_limit = 0;
1138   mock_more_to_flush = 1;
1139   the_scheduler->run();
1140   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1141   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1142
1143   /* Channel is in the pending list now, during that time, we'll trigger a
1144    * wants to write event because maybe the channel buffers were emptied in
1145    * the meantime. This is possible because once the connection outbuf is
1146    * flushed down the low watermark, the scheduler is notified.
1147    *
1148    * We expect the channel to NOT be added in the pending list again and stay
1149    * in PENDING state. */
1150   scheduler_channel_wants_writes(chan1);
1151   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1152   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1153
1154   /* Make it that the channel can write now but has nothing else to flush. We
1155    * expect that it is removed from the pending list and waiting for cells. */
1156   mock_update_socket_info_limit = INT_MAX;
1157   mock_more_to_flush = 0;
1158   the_scheduler->run();
1159   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1160   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
1161
1162   /* While waiting for cells, lets say we were able to write more things on
1163    * the connection outbuf (unlikely that this can happen but let say it
1164    * does). We expect the channel to stay in waiting for cells. */
1165   scheduler_channel_wants_writes(chan1);
1166   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1167   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
1168
1169   /* We'll not put it in the pending list and make the flush cell fail with 0
1170    * cell flushed. We expect that it is put back in waiting for cells. */
1171   scheduler_channel_has_waiting_cells(chan1);
1172   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1173   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1174   mock_flush_some_cells_num = 0;
1175   the_scheduler->run();
1176   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1177   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_FOR_CELLS);
1178
1179   /* Set the channel to a state where it doesn't want to write more. We expect
1180    * that the channel becomes idle. */
1181   scheduler_channel_doesnt_want_writes(chan1);
1182   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1183   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_IDLE);
1184
1185   /* Some cells arrive on the channel now. We expect it to go back in waiting
1186    * to write. You might wonder why it is not put in the pending list? Because
1187    * once the channel becomes OPEN again (the doesn't want to write event only
1188    * occurs if the channel goes in MAINT mode), if there are cells in the
1189    * channel, the wants to write event is triggered thus putting the channel
1190    * in pending mode.
1191    *
1192    * Else, if no cells, it stays IDLE and then once a cell comes in, it should
1193    * go in waiting to write which is a BUG itself because the channel can't be
1194    * scheduled until a second cell comes in. Hopefully, #24554 will fix that
1195    * for KIST. */
1196   scheduler_channel_has_waiting_cells(chan1);
1197   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1198   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_TO_WRITE);
1199
1200   /* Second cell comes in, unfortunately, it won't get scheduled until a wants
1201    * to write event occurs like described above. */
1202   scheduler_channel_has_waiting_cells(chan1);
1203   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 0);
1204   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_WAITING_TO_WRITE);
1205
1206   /* Unblock everything putting the channel in the pending list. */
1207   scheduler_channel_wants_writes(chan1);
1208   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 1);
1209   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1210
1211   /* Testing bug #24700 which is the situation where we have at least two
1212    * different channels in the pending list. The first one gets flushed and
1213    * bytes are written on the wire which triggers a wants to write event
1214    * because the outbuf is below the low watermark. The bug was that this
1215    * exact channel was added back in the pending list because its state wasn't
1216    * PENDING.
1217    *
1218    * The following does some ninja-tsu to try to make it happen. We need two
1219    * different channels so we create a second one and add it to the pending
1220    * list. Then, we have a custom function when we write to kernel that does
1221    * two important things:
1222    *
1223    *  1) Calls scheduler_channel_wants_writes(chan) on the channel.
1224    *  2) Keeps track of how many times it sees the channel going through. If
1225    *     that limit goes > 1, it means we've added the channel twice in the
1226    *     pending list.
1227    *
1228    * In the end, we expect both channels to be in the pending list after this
1229    * scheduler run. */
1230
1231   /* Put the second channel in the pending list. */
1232   scheduler_channel_wants_writes(chan2);
1233   scheduler_channel_has_waiting_cells(chan2);
1234   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 2);
1235   tt_int_op(chan2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1236
1237   /* This makes it that the first pass on socket_can_write() will be true but
1238    * then when a single cell is flushed (514 + 29 bytes), the second call to
1239    * socket_can_write() will be false. If it wasn't sending back false on the
1240    * second run, we end up in an infinite loop of the scheduler. */
1241   mock_update_socket_info_limit = 600;
1242   /* We want to hit "Case 3:" of the scheduler so channel_more_to_flush() is
1243    * true but socket_can_write() has to be false on the second check on the
1244    * channel. */
1245   mock_more_to_flush = 1;
1246   mock_flush_some_cells_num = 1;
1247   MOCK(channel_write_to_kernel, channel_write_to_kernel_mock_trigger_24700);
1248   the_scheduler->run();
1249   tt_int_op(smartlist_len(get_channels_pending()), OP_EQ, 2);
1250   tt_int_op(chan1->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1251   tt_int_op(chan2->scheduler_state, OP_EQ, SCHED_CHAN_PENDING);
1252
1253  done:
1254   chan1->state = chan2->state = CHANNEL_STATE_CLOSED;
1255   chan1->registered = chan2->registered = 0;
1256   channel_free(chan1);
1257   channel_free(chan2);
1258   scheduler_free_all();
1259
1260   UNMOCK(get_options);
1261   UNMOCK(channel_flush_some_cells);
1262   UNMOCK(channel_more_to_flush);
1263   UNMOCK(update_socket_info_impl);
1264   UNMOCK(channel_write_to_kernel);
1265   UNMOCK(channel_should_write_to_kernel);
1266 }
1267
1268 struct testcase_t scheduler_tests[] = {
1269   { "compare_channels", test_scheduler_compare_channels,
1270     TT_FORK, NULL, NULL },
1271   { "channel_states", test_scheduler_channel_states, TT_FORK, NULL, NULL },
1272   { "initfree", test_scheduler_initfree, TT_FORK, NULL, NULL },
1273   { "loop_vanilla", test_scheduler_loop_vanilla, TT_FORK, NULL, NULL },
1274   { "loop_kist", test_scheduler_loop_kist, TT_FORK, NULL, NULL },
1275   { "ns_changed", test_scheduler_ns_changed, TT_FORK, NULL, NULL},
1276   { "should_use_kist", test_scheduler_can_use_kist, TT_FORK, NULL, NULL },
1277   { "kist_pending_list", test_scheduler_kist_pending_list, TT_FORK,
1278     NULL, NULL },
1279   END_OF_TESTCASES
1280 };
1281