folly/experimental/test/FunctionSchedulerTest.cpp

   1 /*
   2  * Copyright 2015 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 #include <gtest/gtest.h>
  24
  25 using namespace folly;
  26 using std::chrono::milliseconds;
  27
  28 namespace {
  29
  30 /*
  31  * Helper functions for controlling how long this test takes.
  32  *
  33  * Using larger intervals here will make the tests less flaky when run on
  34  * heavily loaded systems.  However, this will also make the tests take longer
  35  * to run.
  36  */
  37 static const auto timeFactor = std::chrono::milliseconds(100);
  38 std::chrono::milliseconds testInterval(int n) { return n * timeFactor; }
  39 int getTicksWithinRange(int n, int min, int max) {
  40   assert(min <= max);
  41   n = std::max(min, n);
  42   n = std::min(max, n);
  43   return n;
  44 }
  45 void delay(int n) {
  46   std::chrono::microseconds usec(n * timeFactor);
  47   usleep(usec.count());
  48 }
  49
  50 } // unnamed namespace
  51
  52 TEST(FunctionScheduler, SimpleAdd) {
  53   int total = 0;
  54   FunctionScheduler fs;
  55   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
  56   fs.start();
  57   delay(1);
  58   EXPECT_EQ(2, total);
  59   fs.shutdown();
  60   delay(2);
  61   EXPECT_EQ(2, total);
  62 }
  63
  64 TEST(FunctionScheduler, AddCancel) {
  65   int total = 0;
  66   FunctionScheduler fs;
  67   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
  68   fs.start();
  69   delay(1);
  70   EXPECT_EQ(2, total);
  71   delay(2);
  72   EXPECT_EQ(4, total);
  73   EXPECT_TRUE(fs.cancelFunction("add2"));
  74   EXPECT_FALSE(fs.cancelFunction("NO SUCH FUNC"));
  75   delay(2);
  76   EXPECT_EQ(4, total);
  77   fs.addFunction([&] { total += 1; }, testInterval(2), "add2");
  78   EXPECT_FALSE(fs.start()); // already running
  79   delay(1);
  80   EXPECT_EQ(5, total);
  81   delay(2);
  82   EXPECT_EQ(6, total);
  83   fs.shutdown();
  84 }
  85
  86 TEST(FunctionScheduler, AddCancel2) {
  87   int total = 0;
  88   FunctionScheduler fs;
  89
  90   // Test adds and cancels while the scheduler is stopped
  91   EXPECT_FALSE(fs.cancelFunction("add2"));
  92   fs.addFunction([&] { total += 1; }, testInterval(2), "add2");
  93   EXPECT_TRUE(fs.cancelFunction("add2"));
  94   EXPECT_FALSE(fs.cancelFunction("add2"));
  95   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
  96   fs.addFunction([&] { total += 3; }, testInterval(3), "add3");
  97
  98   EXPECT_EQ(0, total);
  99   fs.start();
 100   delay(1);
 101   EXPECT_EQ(5, total);
 102
 103   // Cancel add2 while the scheduler is running
 104   EXPECT_TRUE(fs.cancelFunction("add2"));
 105   EXPECT_FALSE(fs.cancelFunction("add2"));
 106   EXPECT_FALSE(fs.cancelFunction("bogus"));
 107
 108   delay(3);
 109   EXPECT_EQ(8, total);
 110   EXPECT_TRUE(fs.cancelFunction("add3"));
 111
 112   // Test a function that cancels itself
 113   int selfCancelCount = 0;
 114   fs.addFunction(
 115       [&] {
 116         ++selfCancelCount;
 117         if (selfCancelCount > 2) {
 118           fs.cancelFunction("selfCancel");
 119         }
 120       },
 121       testInterval(1), "selfCancel", testInterval(1));
 122   delay(4);
 123   EXPECT_EQ(3, selfCancelCount);
 124   EXPECT_FALSE(fs.cancelFunction("selfCancel"));
 125
 126   // Test a function that schedules another function
 127   int adderCount = 0;
 128   int fn2Count = 0;
 129   auto fn2 = [&] { ++fn2Count; };
 130   auto fnAdder = [&] {
 131     ++adderCount;
 132     if (adderCount == 2) {
 133       fs.addFunction(fn2, testInterval(3), "fn2", testInterval(2));
 134     }
 135   };
 136   fs.addFunction(fnAdder, testInterval(4), "adder");
 137   // t0: adder fires
 138   delay(1); // t1
 139   EXPECT_EQ(1, adderCount);
 140   EXPECT_EQ(0, fn2Count);
 141   // t4: adder fires, schedules fn2
 142   delay(4); // t5
 143   EXPECT_EQ(2, adderCount);
 144   EXPECT_EQ(0, fn2Count);
 145   // t6: fn2 fires
 146   delay(2); // t7
 147   EXPECT_EQ(2, adderCount);
 148   EXPECT_EQ(1, fn2Count);
 149   // t8: adder fires
 150   // t9: fn2 fires
 151   delay(3); // t10
 152   EXPECT_EQ(3, adderCount);
 153   EXPECT_EQ(2, fn2Count);
 154   EXPECT_TRUE(fs.cancelFunction("fn2"));
 155   EXPECT_TRUE(fs.cancelFunction("adder"));
 156   delay(5); // t10
 157   EXPECT_EQ(3, adderCount);
 158   EXPECT_EQ(2, fn2Count);
 159
 160   EXPECT_EQ(8, total);
 161   EXPECT_EQ(3, selfCancelCount);
 162 }
 163
 164 TEST(FunctionScheduler, AddMultiple) {
 165   int total = 0;
 166   FunctionScheduler fs;
 167   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 168   fs.addFunction([&] { total += 3; }, testInterval(3), "add3");
 169   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(2), "add2"),
 170                std::invalid_argument); // function name already exists
 171
 172   fs.start();
 173   delay(1);
 174   EXPECT_EQ(5, total);
 175   delay(4);
 176   EXPECT_EQ(12, total);
 177   EXPECT_TRUE(fs.cancelFunction("add2"));
 178   delay(2);
 179   EXPECT_EQ(15, total);
 180   fs.shutdown();
 181   delay(3);
 182   EXPECT_EQ(15, total);
 183   fs.shutdown();
 184 }
 185
 186 TEST(FunctionScheduler, AddAfterStart) {
 187   int total = 0;
 188   FunctionScheduler fs;
 189   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 190   fs.addFunction([&] { total += 3; }, testInterval(2), "add3");
 191   fs.start();
 192   delay(3);
 193   EXPECT_EQ(10, total);
 194   fs.addFunction([&] { total += 2; }, testInterval(3), "add22");
 195   delay(2);
 196   EXPECT_EQ(17, total);
 197 }
 198
 199 TEST(FunctionScheduler, ShutdownStart) {
 200   int total = 0;
 201   FunctionScheduler fs;
 202   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 203   fs.start();
 204   delay(1);
 205   fs.shutdown();
 206   fs.start();
 207   delay(1);
 208   EXPECT_EQ(4, total);
 209   EXPECT_FALSE(fs.cancelFunction("add3")); // non existing
 210   delay(2);
 211   EXPECT_EQ(6, total);
 212 }
 213
 214 TEST(FunctionScheduler, AddInvalid) {
 215   int total = 0;
 216   FunctionScheduler fs;
 217   // interval may not be negative
 218   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(-1), "add2"),
 219                std::invalid_argument);
 220
 221   EXPECT_FALSE(fs.cancelFunction("addNoFunc"));
 222 }
 223
 224 TEST(FunctionScheduler, NoFunctions) {
 225   FunctionScheduler fs;
 226   EXPECT_TRUE(fs.start());
 227   fs.shutdown();
 228   FunctionScheduler fs2;
 229   fs2.shutdown();
 230 }
 231
 232 TEST(FunctionScheduler, AddWhileRunning) {
 233   int total = 0;
 234   FunctionScheduler fs;
 235   fs.start();
 236   delay(1);
 237   fs.addFunction([&] { total += 2; }, testInterval(2), "add2");
 238   // The function should be invoked nearly immediately when we add it
 239   // and the FunctionScheduler is already running
 240   usleep(50000);
 241   EXPECT_EQ(2, total);
 242   delay(2);
 243   EXPECT_EQ(4, total);
 244 }
 245
 246 TEST(FunctionScheduler, NoShutdown) {
 247   int total = 0;
 248   {
 249     FunctionScheduler fs;
 250     fs.addFunction([&] { total += 2; }, testInterval(1), "add2");
 251     fs.start();
 252     usleep(50000);
 253     EXPECT_EQ(2, total);
 254   }
 255   // Destroyed the FunctionScheduler without calling shutdown.
 256   // Everything should have been cleaned up, and the function will no longer
 257   // get called.
 258   delay(2);
 259   EXPECT_EQ(2, total);
 260 }
 261
 262 TEST(FunctionScheduler, StartDelay) {
 263   int total = 0;
 264   FunctionScheduler fs;
 265   fs.addFunction([&] { total += 2; }, testInterval(2), "add2",
 266                  testInterval(2));
 267   fs.addFunction([&] { total += 3; }, testInterval(3), "add3",
 268                  testInterval(2));
 269   EXPECT_THROW(fs.addFunction([&] { total += 2; }, testInterval(3),
 270                               "addX", testInterval(-1)),
 271                std::invalid_argument);
 272   fs.start();
 273   delay(1); // t1
 274   EXPECT_EQ(0, total);
 275   // t2 : add2 total=2
 276   // t2 : add3 total=5
 277   delay(2); // t3
 278   EXPECT_EQ(5, total);
 279   // t4 : add2: total=7
 280   // t5 : add3: total=10
 281   // t6 : add2: total=12
 282   delay(4); // t7
 283   EXPECT_EQ(12, total);
 284   fs.cancelFunction("add2");
 285   // t8 : add3: total=15
 286   delay(2); // t9
 287   EXPECT_EQ(15, total);
 288   fs.shutdown();
 289   delay(3);
 290   EXPECT_EQ(15, total);
 291   fs.shutdown();
 292 }
 293
 294 TEST(FunctionScheduler, NoSteadyCatchup) {
 295   std::atomic<int> ticks(0);
 296   FunctionScheduler fs;
 297   // fs.setSteady(false); is the default
 298   fs.addFunction([&ticks] {
 299                    if (++ticks == 2) {
 300                      std::this_thread::sleep_for(
 301                          std::chrono::milliseconds(200));
 302                    }
 303                  },
 304                  milliseconds(5));
 305   fs.start();
 306   std::this_thread::sleep_for(std::chrono::milliseconds(500));
 307
 308   // no steady catch up means we'd tick once for 200ms, then remaining
 309   // 300ms / 5 = 60 times
 310   EXPECT_LE(ticks.load(), 61);
 311 }
 312
 313 TEST(FunctionScheduler, SteadyCatchup) {
 314   std::atomic<int> ticks(0);
 315   FunctionScheduler fs;
 316   fs.setSteady(true);
 317   fs.addFunction([&ticks] {
 318                    if (++ticks == 2) {
 319                      std::this_thread::sleep_for(
 320                          std::chrono::milliseconds(200));
 321                    }
 322                  },
 323                  milliseconds(5));
 324   fs.start();
 325
 326   std::this_thread::sleep_for(std::chrono::milliseconds(500));
 327
 328   // tick every 5ms. Despite tick == 2 is slow, later ticks should be fast
 329   // enough to catch back up to schedule
 330   EXPECT_NEAR(100, ticks.load(), 10);
 331 }
 332
 333 TEST(FunctionScheduler, UniformDistribution) {
 334   int total = 0;
 335   const int kTicks = 2;
 336   std::chrono::milliseconds minInterval =
 337       testInterval(kTicks) - (timeFactor / 5);
 338   std::chrono::milliseconds maxInterval =
 339       testInterval(kTicks) + (timeFactor / 5);
 340   FunctionScheduler fs;
 341   fs.addFunctionUniformDistribution([&] { total += 2; },
 342                                     minInterval,
 343                                     maxInterval,
 344                                     "UniformDistribution",
 345                                     std::chrono::milliseconds(0));
 346   fs.start();
 347   delay(1);
 348   EXPECT_EQ(2, total);
 349   delay(kTicks);
 350   EXPECT_EQ(4, total);
 351   delay(kTicks);
 352   EXPECT_EQ(6, total);
 353   fs.shutdown();
 354   delay(2);
 355   EXPECT_EQ(6, total);
 356 }
 357
 358 TEST(FunctionScheduler, ExponentialBackoff) {
 359   int total = 0;
 360   int expectedInterval = 0;
 361   int nextInterval = 2;
 362   FunctionScheduler fs;
 363   fs.addFunctionGenericDistribution(
 364       [&] { total += 2; },
 365       [&expectedInterval, nextInterval]() mutable {
 366         expectedInterval = nextInterval;
 367         nextInterval *= nextInterval;
 368         return testInterval(expectedInterval);
 369       },
 370       "ExponentialBackoff",
 371       "2^n * 100ms",
 372       std::chrono::milliseconds(0));
 373   fs.start();
 374   delay(1);
 375   EXPECT_EQ(2, total);
 376   delay(expectedInterval);
 377   EXPECT_EQ(4, total);
 378   delay(expectedInterval);
 379   EXPECT_EQ(6, total);
 380   fs.shutdown();
 381   delay(2);
 382   EXPECT_EQ(6, total);
 383 }
 384
 385 TEST(FunctionScheduler, GammaIntervalDistribution) {
 386   int total = 0;
 387   int expectedInterval = 0;
 388   FunctionScheduler fs;
 389   std::default_random_engine generator(folly::Random::rand32());
 390   // The alpha and beta arguments are selected, somewhat randomly, to be 2.0.
 391   // These values do not matter much in this test, as we are not testing the
 392   // std::gamma_distribution itself...
 393   std::gamma_distribution<double> gamma(2.0, 2.0);
 394   fs.addFunctionGenericDistribution(
 395       [&] { total += 2; },
 396       [&expectedInterval, generator, gamma]() mutable {
 397         expectedInterval =
 398             getTicksWithinRange(static_cast<int>(gamma(generator)), 2, 10);
 399         return testInterval(expectedInterval);
 400       },
 401       "GammaDistribution",
 402       "gamma(2.0,2.0)*100ms",
 403       std::chrono::milliseconds(0));
 404   fs.start();
 405   delay(1);
 406   EXPECT_EQ(2, total);
 407   delay(expectedInterval);
 408   EXPECT_EQ(4, total);
 409   delay(expectedInterval);
 410   EXPECT_EQ(6, total);
 411   fs.shutdown();
 412   delay(2);
 413   EXPECT_EQ(6, total);
 414 }