folly/experimental/test/FunctionSchedulerTest.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include <folly/experimental/FunctionScheduler.h>
  17
  18 #include <algorithm>
  19 #include <atomic>
  20 #include <cassert>
  21 #include <random>
  22 #include <folly/Random.h>
  23
  24 #include <folly/portability/GTest.h>
  25
  26 using namespace folly;
  27 using std::chrono::milliseconds;
  28
  29 namespace {
  30
  31 /*
  32  * Helper functions for controlling how long this test takes.
  33  *
  34  * Using larger intervals here will make the tests less flaky when run on
  35  * heavily loaded systems.  However, this will also make the tests take longer
  36  * to run.
  37  */
  38 static const auto timeFactor = std::chrono::milliseconds(100);
  39 std::chrono::milliseconds testInterval(int n) { return n * timeFactor; }
  40 int getTicksWithinRange(int n, int min, int max) {
  41   assert(min <= max);
  42   n = std::max(min, n);
  43   n = std::min(max, n);
  44   return n;
  45 }
  46 void delay(int n) {
  47   std::chrono::microseconds usec(n * timeFactor);
  48   usleep(usec.count());
  49 }
  50
  51 } // unnamed namespace
  52
  53 TEST(FunctionScheduler, StartAndShutdown) {
  54   FunctionScheduler fs;
  55   EXPECT_TRUE(fs.start());
  56   EXPECT_FALSE(fs.start());
  57   EXPECT_TRUE(fs.shutdown());
  58   EXPECT_FALSE(fs.shutdown());
  59   // start again
  60   EXPECT_TRUE(fs.start());
  61   EXPECT_FALSE(fs.start());
  62   EXPECT_TRUE(fs.shutdown());
  63   EXPECT_FALSE(fs.shutdown());
  64 }
  65
  66 TEST(FunctionScheduler, SimpleAdd) {
  67   int total = 0;
  68   FunctionScheduler fs;
  69   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
  70   fs.start();
  71   delay(1);
  72   EXPECT_EQ(2, total);
  73   fs.shutdown();
  74   delay(2);
  75   EXPECT_EQ(2, total);
  76 }
  77
  78 TEST(FunctionScheduler, AddCancel) {
  79   int total = 0;
  80   FunctionScheduler fs;
  81   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
  82   fs.start();
  83   delay(1);
  84   EXPECT_EQ(2, total);
  85   delay(2);
  86   EXPECT_EQ(4, total);
  87   EXPECT_TRUE(fs.cancelFunction("add2"));
  88   EXPECT_FALSE(fs.cancelFunction("NO SUCH FUNC"));
  89   delay(2);
  90   EXPECT_EQ(4, total);
  91   fs.addFunction([&] { total += 1; }, testInterval(2), "add2");
  92   delay(1);
  93   EXPECT_EQ(5, total);
  94   delay(2);
  95   EXPECT_EQ(6, total);
  96   fs.shutdown();
  97 }
  98
  99 TEST(FunctionScheduler, AddCancel2) {
 100   int total = 0;
 101   FunctionScheduler fs;
 102
 103   // Test adds and cancels while the scheduler is stopped
 104   EXPECT_FALSE(fs.cancelFunction("add2"));
 105   fs.addFunction([&] { total += 1; }, testInterval(2), "add2");
 106   EXPECT_TRUE(fs.cancelFunction("add2"));
 107   EXPECT_FALSE(fs.cancelFunction("add2"));
 108   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 109   fs.addFunction([&] { total += 3; }, testInterval(3), "add3");
 110
 111   EXPECT_EQ(0, total);
 112   fs.start();
 113   delay(1);
 114   EXPECT_EQ(5, total);
 115
 116   // Cancel add2 while the scheduler is running
 117   EXPECT_TRUE(fs.cancelFunction("add2"));
 118   EXPECT_FALSE(fs.cancelFunction("add2"));
 119   EXPECT_FALSE(fs.cancelFunction("bogus"));
 120
 121   delay(3);
 122   EXPECT_EQ(8, total);
 123   EXPECT_TRUE(fs.cancelFunction("add3"));
 124
 125   // Test a function that cancels itself
 126   int selfCancelCount = 0;
 127   fs.addFunction(
 128       [&] {
 129         ++selfCancelCount;
 130         if (selfCancelCount > 2) {
 131           fs.cancelFunction("selfCancel");
 132         }
 133       },
 134       testInterval(1), "selfCancel", testInterval(1));
 135   delay(4);
 136   EXPECT_EQ(3, selfCancelCount);
 137   EXPECT_FALSE(fs.cancelFunction("selfCancel"));
 138
 139   // Test a function that schedules another function
 140   int adderCount = 0;
 141   int fn2Count = 0;
 142   auto fn2 = [&] { ++fn2Count; };
 143   auto fnAdder = [&] {
 144     ++adderCount;
 145     if (adderCount == 2) {
 146       fs.addFunction(fn2, testInterval(3), "fn2", testInterval(2));
 147     }
 148   };
 149   fs.addFunction(fnAdder, testInterval(4), "adder");
 150   // t0: adder fires
 151   delay(1); // t1
 152   EXPECT_EQ(1, adderCount);
 153   EXPECT_EQ(0, fn2Count);
 154   // t4: adder fires, schedules fn2
 155   delay(4); // t5
 156   EXPECT_EQ(2, adderCount);
 157   EXPECT_EQ(0, fn2Count);
 158   // t6: fn2 fires
 159   delay(2); // t7
 160   EXPECT_EQ(2, adderCount);
 161   EXPECT_EQ(1, fn2Count);
 162   // t8: adder fires
 163   // t9: fn2 fires
 164   delay(3); // t10
 165   EXPECT_EQ(3, adderCount);
 166   EXPECT_EQ(2, fn2Count);
 167   EXPECT_TRUE(fs.cancelFunction("fn2"));
 168   EXPECT_TRUE(fs.cancelFunction("adder"));
 169   delay(5); // t10
 170   EXPECT_EQ(3, adderCount);
 171   EXPECT_EQ(2, fn2Count);
 172
 173   EXPECT_EQ(8, total);
 174   EXPECT_EQ(3, selfCancelCount);
 175 }
 176
 177 TEST(FunctionScheduler, AddMultiple) {
 178   int total = 0;
 179   FunctionScheduler fs;
 180   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 181   fs.addFunction([&] { total += 3; }, testInterval(3), "add3");
 182   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(2), "add2"),
 183                std::invalid_argument); // function name already exists
 184
 185   fs.start();
 186   delay(1);
 187   EXPECT_EQ(5, total);
 188   delay(4);
 189   EXPECT_EQ(12, total);
 190   EXPECT_TRUE(fs.cancelFunction("add2"));
 191   delay(2);
 192   EXPECT_EQ(15, total);
 193   fs.shutdown();
 194   delay(3);
 195   EXPECT_EQ(15, total);
 196   fs.shutdown();
 197 }
 198
 199 TEST(FunctionScheduler, AddAfterStart) {
 200   int total = 0;
 201   FunctionScheduler fs;
 202   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 203   fs.addFunction([&] { total += 3; }, testInterval(2), "add3");
 204   fs.start();
 205   delay(3);
 206   EXPECT_EQ(10, total);
 207   fs.addFunction([&] { total += 2; }, testInterval(3), "add22");
 208   delay(2);
 209   EXPECT_EQ(17, total);
 210 }
 211
 212 TEST(FunctionScheduler, ShutdownStart) {
 213   int total = 0;
 214   FunctionScheduler fs;
 215   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 216   fs.start();
 217   delay(1);
 218   fs.shutdown();
 219   fs.start();
 220   delay(1);
 221   EXPECT_EQ(4, total);
 222   EXPECT_FALSE(fs.cancelFunction("add3")); // non existing
 223   delay(2);
 224   EXPECT_EQ(6, total);
 225 }
 226
 227 TEST(FunctionScheduler, ResetFunc) {
 228   int total = 0;
 229   FunctionScheduler fs;
 230   fs.addFunction([&] { total += 2; }, testInterval(3), "add2");
 231   fs.addFunction([&] { total += 3; }, testInterval(3), "add3");
 232   fs.start();
 233   delay(1);
 234   EXPECT_EQ(5, total);
 235   EXPECT_FALSE(fs.resetFunctionTimer("NON_EXISTING"));
 236   EXPECT_TRUE(fs.resetFunctionTimer("add2"));
 237   delay(1);
 238   // t2: after the reset, add2 should have been invoked immediately
 239   EXPECT_EQ(7, total);
 240   usleep(150000);
 241   // t3.5: add3 should have been invoked. add2 should not
 242   EXPECT_EQ(10, total);
 243   delay(1);
 244   // t4.5: add2 should have been invoked once more (it was reset at t1)
 245   EXPECT_EQ(12, total);
 246 }
 247
 248 TEST(FunctionScheduler, AddInvalid) {
 249   int total = 0;
 250   FunctionScheduler fs;
 251   // interval may not be negative
 252   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(-1), "add2"),
 253                std::invalid_argument);
 254
 255   EXPECT_FALSE(fs.cancelFunction("addNoFunc"));
 256 }
 257
 258 TEST(FunctionScheduler, NoFunctions) {
 259   FunctionScheduler fs;
 260   EXPECT_TRUE(fs.start());
 261   fs.shutdown();
 262   FunctionScheduler fs2;
 263   fs2.shutdown();
 264 }
 265
 266 TEST(FunctionScheduler, AddWhileRunning) {
 267   int total = 0;
 268   FunctionScheduler fs;
 269   fs.start();
 270   delay(1);
 271   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 272   // The function should be invoked nearly immediately when we add it
 273   // and the FunctionScheduler is already running
 274   usleep(50000);
 275   EXPECT_EQ(2, total);
 276   delay(2);
 277   EXPECT_EQ(4, total);
 278 }
 279
 280 TEST(FunctionScheduler, NoShutdown) {
 281   int total = 0;
 282   {
 283     FunctionScheduler fs;
 284     fs.addFunction([&] { total += 2; }, testInterval(1), "add2");
 285     fs.start();
 286     usleep(50000);
 287     EXPECT_EQ(2, total);
 288   }
 289   // Destroyed the FunctionScheduler without calling shutdown.
 290   // Everything should have been cleaned up, and the function will no longer
 291   // get called.
 292   delay(2);
 293   EXPECT_EQ(2, total);
 294 }
 295
 296 TEST(FunctionScheduler, StartDelay) {
 297   int total = 0;
 298   FunctionScheduler fs;
 299   fs.addFunction([&] { total += 2; }, testInterval(2), "add2",
 300                  testInterval(2));
 301   fs.addFunction([&] { total += 3; }, testInterval(3), "add3",
 302                  testInterval(2));
 303   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(3),
 304                               "addX", testInterval(-1)),
 305                std::invalid_argument);
 306   fs.start();
 307   delay(1); // t1
 308   EXPECT_EQ(0, total);
 309   // t2 : add2 total=2
 310   // t2 : add3 total=5
 311   delay(2); // t3
 312   EXPECT_EQ(5, total);
 313   // t4 : add2: total=7
 314   // t5 : add3: total=10
 315   // t6 : add2: total=12
 316   delay(4); // t7
 317   EXPECT_EQ(12, total);
 318   fs.cancelFunction("add2");
 319   // t8 : add3: total=15
 320   delay(2); // t9
 321   EXPECT_EQ(15, total);
 322   fs.shutdown();
 323   delay(3);
 324   EXPECT_EQ(15, total);
 325   fs.shutdown();
 326 }
 327
 328 TEST(FunctionScheduler, NoSteadyCatchup) {
 329   std::atomic<int> ticks(0);
 330   FunctionScheduler fs;
 331   // fs.setSteady(false); is the default
 332   fs.addFunction([&ticks] {
 333                    if (++ticks == 2) {
 334                      std::this_thread::sleep_for(
 335                          std::chrono::milliseconds(200));
 336                    }
 337                  },
 338                  milliseconds(5));
 339   fs.start();
 340   std::this_thread::sleep_for(std::chrono::milliseconds(500));
 341
 342   // no steady catch up means we'd tick once for 200ms, then remaining
 343   // 300ms / 5 = 60 times
 344   EXPECT_LE(ticks.load(), 61);
 345 }
 346
 347 TEST(FunctionScheduler, SteadyCatchup) {
 348   std::atomic<int> ticks(0);
 349   FunctionScheduler fs;
 350   fs.setSteady(true);
 351   fs.addFunction([&ticks] {
 352                    if (++ticks == 2) {
 353                      std::this_thread::sleep_for(
 354                          std::chrono::milliseconds(200));
 355                    }
 356                  },
 357                  milliseconds(5));
 358   fs.start();
 359
 360   std::this_thread::sleep_for(std::chrono::milliseconds(500));
 361
 362   // tick every 5ms. Despite tick == 2 is slow, later ticks should be fast
 363   // enough to catch back up to schedule
 364   EXPECT_NEAR(100, ticks.load(), 10);
 365 }
 366
 367 TEST(FunctionScheduler, UniformDistribution) {
 368   int total = 0;
 369   const int kTicks = 2;
 370   std::chrono::milliseconds minInterval =
 371       testInterval(kTicks) - (timeFactor / 5);
 372   std::chrono::milliseconds maxInterval =
 373       testInterval(kTicks) + (timeFactor / 5);
 374   FunctionScheduler fs;
 375   fs.addFunctionUniformDistribution([&] { total += 2; },
 376                                     minInterval,
 377                                     maxInterval,
 378                                     "UniformDistribution",
 379                                     std::chrono::milliseconds(0));
 380   fs.start();
 381   delay(1);
 382   EXPECT_EQ(2, total);
 383   delay(kTicks);
 384   EXPECT_EQ(4, total);
 385   delay(kTicks);
 386   EXPECT_EQ(6, total);
 387   fs.shutdown();
 388   delay(2);
 389   EXPECT_EQ(6, total);
 390 }
 391
 392 TEST(FunctionScheduler, ExponentialBackoff) {
 393   int total = 0;
 394   int expectedInterval = 0;
 395   int nextInterval = 2;
 396   FunctionScheduler fs;
 397   fs.addFunctionGenericDistribution(
 398       [&] { total += 2; },
 399       [&expectedInterval, nextInterval]() mutable {
 400         expectedInterval = nextInterval;
 401         nextInterval *= nextInterval;
 402         return testInterval(expectedInterval);
 403       },
 404       "ExponentialBackoff",
 405       "2^n * 100ms",
 406       std::chrono::milliseconds(0));
 407   fs.start();
 408   delay(1);
 409   EXPECT_EQ(2, total);
 410   delay(expectedInterval);
 411   EXPECT_EQ(4, total);
 412   delay(expectedInterval);
 413   EXPECT_EQ(6, total);
 414   fs.shutdown();
 415   delay(2);
 416   EXPECT_EQ(6, total);
 417 }
 418
 419 TEST(FunctionScheduler, GammaIntervalDistribution) {
 420   int total = 0;
 421   int expectedInterval = 0;
 422   FunctionScheduler fs;
 423   std::default_random_engine generator(folly::Random::rand32());
 424   // The alpha and beta arguments are selected, somewhat randomly, to be 2.0.
 425   // These values do not matter much in this test, as we are not testing the
 426   // std::gamma_distribution itself...
 427   std::gamma_distribution<double> gamma(2.0, 2.0);
 428   fs.addFunctionGenericDistribution(
 429       [&] { total += 2; },
 430       [&expectedInterval, generator, gamma]() mutable {
 431         expectedInterval =
 432             getTicksWithinRange(static_cast<int>(gamma(generator)), 2, 10);
 433         return testInterval(expectedInterval);
 434       },
 435       "GammaDistribution",
 436       "gamma(2.0,2.0)*100ms",
 437       std::chrono::milliseconds(0));
 438   fs.start();
 439   delay(1);
 440   EXPECT_EQ(2, total);
 441   delay(expectedInterval);
 442   EXPECT_EQ(4, total);
 443   delay(expectedInterval);
 444   EXPECT_EQ(6, total);
 445   fs.shutdown();
 446   delay(2);
 447   EXPECT_EQ(6, total);
 448 }
 449
 450 TEST(FunctionScheduler, AddWithRunOnce) {
 451   int total = 0;
 452   FunctionScheduler fs;
 453   fs.addFunctionOnce([&] { total += 2; }, "add2");
 454   fs.start();
 455   delay(1);
 456   EXPECT_EQ(2, total);
 457   delay(2);
 458   EXPECT_EQ(2, total);
 459
 460   fs.addFunctionOnce([&] { total += 2; }, "add2");
 461   delay(1);
 462   EXPECT_EQ(4, total);
 463   delay(2);
 464   EXPECT_EQ(4, total);
 465
 466   fs.shutdown();
 467 }
 468
 469 TEST(FunctionScheduler, cancelFunctionAndWait) {
 470   int total = 0;
 471   FunctionScheduler fs;
 472   fs.addFunction(
 473       [&] {
 474         delay(5);
 475         total += 2;
 476       },
 477       testInterval(100),
 478       "add2");
 479
 480   fs.start();
 481   delay(1);
 482   EXPECT_EQ(0, total); // add2 is still sleeping
 483
 484   EXPECT_TRUE(fs.cancelFunctionAndWait("add2"));
 485   EXPECT_EQ(2, total); // add2 should have completed
 486
 487   EXPECT_FALSE(fs.cancelFunction("add2")); // add2 has been canceled
 488   fs.shutdown();
 489 }
 490
 491 TEST(FunctionScheduler, cancelAllFunctionsAndWait) {
 492   int total = 0;
 493   FunctionScheduler fs;
 494
 495   fs.addFunction(
 496       [&] {
 497         delay(5);
 498         total += 2;
 499       },
 500       testInterval(100),
 501       "add2");
 502
 503   fs.start();
 504   delay(1);
 505   EXPECT_EQ(0, total); // add2 is still sleeping
 506
 507   fs.cancelAllFunctionsAndWait();
 508   EXPECT_EQ(2, total);
 509
 510   EXPECT_FALSE(fs.cancelFunction("add2")); // add2 has been canceled
 511   fs.shutdown();
 512 }