folly/io/async/test/HHWheelTimerTest.cpp

   1 /*
   2  * Licensed to the Apache Software Foundation (ASF) under one
   3  * or more contributor license agreements. See the NOTICE file
   4  * distributed with this work for additional information
   5  * regarding copyright ownership. The ASF licenses this file
   6  * to you under the Apache License, Version 2.0 (the
   7  * "License"); you may not use this file except in compliance
   8  * with the License. You may obtain a copy of the License at
   9  *
  10  *   http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing,
  13  * software distributed under the License is distributed on an
  14  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  15  * KIND, either express or implied. See the License for the
  16  * specific language governing permissions and limitations
  17  * under the License.
  18  */
  19 #include <folly/io/async/HHWheelTimer.h>
  20 #include <folly/io/async/EventBase.h>
  21 #include <folly/io/async/test/UndelayedDestruction.h>
  22 #include <folly/io/async/test/Util.h>
  23
  24 #include <gtest/gtest.h>
  25 #include <vector>
  26
  27 using namespace folly;
  28 using std::chrono::milliseconds;
  29
  30 typedef UndelayedDestruction<HHWheelTimer> StackWheelTimer;
  31
  32 class TestTimeout : public HHWheelTimer::Callback {
  33  public:
  34   TestTimeout() {}
  35   TestTimeout(HHWheelTimer* t, milliseconds timeout) {
  36     t->scheduleTimeout(this, timeout);
  37   }
  38   virtual void timeoutExpired() noexcept {
  39     timestamps.push_back(TimePoint());
  40     if (fn) {
  41       fn();
  42     }
  43   }
  44
  45   std::deque<TimePoint> timestamps;
  46   std::function<void()> fn;
  47 };
  48
  49
  50 class TestTimeoutDelayed : public TestTimeout {
  51  protected:
  52     std::chrono::milliseconds getCurTime() override {
  53       return std::chrono::duration_cast<std::chrono::milliseconds>(
  54         std::chrono::steady_clock::now().time_since_epoch()) -
  55         milliseconds(5);
  56     }
  57 };
  58
  59 struct HHWheelTimerTest : public ::testing::Test {
  60   EventBase eventBase;
  61 };
  62
  63 /*
  64  * Test firing some simple timeouts that are fired once and never rescheduled
  65  */
  66 TEST_F(HHWheelTimerTest, FireOnce) {
  67   StackWheelTimer t(&eventBase, milliseconds(1));
  68
  69   const HHWheelTimer::Callback* nullCallback = nullptr;
  70
  71   TestTimeout t1;
  72   TestTimeout t2;
  73   TestTimeout t3;
  74
  75   ASSERT_EQ(t.count(), 0);
  76
  77   t.scheduleTimeout(&t1, milliseconds(5));
  78   t.scheduleTimeout(&t2, milliseconds(5));
  79   // Verify scheduling it twice cancels, then schedules.
  80   // Should only get one callback.
  81   t.scheduleTimeout(&t2, milliseconds(5));
  82   t.scheduleTimeout(&t3, milliseconds(10));
  83
  84   ASSERT_EQ(t.count(), 3);
  85
  86   TimePoint start;
  87   eventBase.loop();
  88   TimePoint end;
  89
  90   ASSERT_EQ(t1.timestamps.size(), 1);
  91   ASSERT_EQ(t2.timestamps.size(), 1);
  92   ASSERT_EQ(t3.timestamps.size(), 1);
  93
  94   ASSERT_EQ(t.count(), 0);
  95
  96   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
  97   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
  98   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
  99   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 100 }
 101
 102 /*
 103  * Test scheduling a timeout from another timeout callback.
 104  */
 105 TEST_F(HHWheelTimerTest, TestSchedulingWithinCallback) {
 106   StackWheelTimer t(&eventBase, milliseconds(10));
 107   const HHWheelTimer::Callback* nullCallback = nullptr;
 108
 109   TestTimeout t1;
 110   // Delayed to simulate the steady_clock counter lagging
 111   TestTimeoutDelayed t2;
 112
 113   t.scheduleTimeout(&t1, milliseconds(500));
 114   t1.fn = [&] { t.scheduleTimeout(&t2, milliseconds(1)); };
 115   // If t is in an inconsistent state, detachEventBase should fail.
 116   t2.fn = [&] { t.detachEventBase(); };
 117
 118   ASSERT_EQ(t.count(), 1);
 119
 120   eventBase.loop();
 121
 122   ASSERT_EQ(t.count(), 0);
 123   ASSERT_EQ(t1.timestamps.size(), 1);
 124   ASSERT_EQ(t2.timestamps.size(), 1);
 125 }
 126
 127 /*
 128  * Test cancelling a timeout when it is scheduled to be fired right away.
 129  */
 130
 131 TEST_F(HHWheelTimerTest, CancelTimeout) {
 132   StackWheelTimer t(&eventBase, milliseconds(1));
 133
 134   // Create several timeouts that will all fire in 5ms.
 135   TestTimeout t5_1(&t, milliseconds(5));
 136   TestTimeout t5_2(&t, milliseconds(5));
 137   TestTimeout t5_3(&t, milliseconds(5));
 138   TestTimeout t5_4(&t, milliseconds(5));
 139   TestTimeout t5_5(&t, milliseconds(5));
 140
 141   // Also create a few timeouts to fire in 10ms
 142   TestTimeout t10_1(&t, milliseconds(10));
 143   TestTimeout t10_2(&t, milliseconds(10));
 144   TestTimeout t10_3(&t, milliseconds(10));
 145
 146   TestTimeout t20_1(&t, milliseconds(20));
 147   TestTimeout t20_2(&t, milliseconds(20));
 148
 149   // Have t5_1 cancel t5_2 and t5_4.
 150   //
 151   // Cancelling t5_2 will test cancelling a timeout that is at the head of the
 152   // list and ready to be fired.
 153   //
 154   // Cancelling t5_4 will test cancelling a timeout in the middle of the list
 155   t5_1.fn = [&] {
 156     t5_2.cancelTimeout();
 157     t5_4.cancelTimeout();
 158   };
 159
 160   // Have t5_3 cancel t5_5.
 161   // This will test cancelling the last remaining timeout.
 162   //
 163   // Then have t5_3 reschedule itself.
 164   t5_3.fn = [&] {
 165     t5_5.cancelTimeout();
 166     // Reset our function so we won't continually reschedule ourself
 167     std::function<void()> fnDtorGuard;
 168     t5_3.fn.swap(fnDtorGuard);
 169     t.scheduleTimeout(&t5_3, milliseconds(5));
 170
 171     // Also test cancelling timeouts in another timeset that isn't ready to
 172     // fire yet.
 173     //
 174     // Cancel the middle timeout in ts10.
 175     t10_2.cancelTimeout();
 176     // Cancel both the timeouts in ts20.
 177     t20_1.cancelTimeout();
 178     t20_2.cancelTimeout();
 179   };
 180
 181   TimePoint start;
 182   eventBase.loop();
 183   TimePoint end;
 184
 185   ASSERT_EQ(t5_1.timestamps.size(), 1);
 186   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 187
 188   ASSERT_EQ(t5_3.timestamps.size(), 2);
 189   T_CHECK_TIMEOUT(start, t5_3.timestamps[0], milliseconds(5));
 190   T_CHECK_TIMEOUT(t5_3.timestamps[0], t5_3.timestamps[1], milliseconds(5));
 191
 192   ASSERT_EQ(t10_1.timestamps.size(), 1);
 193   T_CHECK_TIMEOUT(start, t10_1.timestamps[0], milliseconds(10));
 194   ASSERT_EQ(t10_3.timestamps.size(), 1);
 195   T_CHECK_TIMEOUT(start, t10_3.timestamps[0], milliseconds(10));
 196
 197   // Cancelled timeouts
 198   ASSERT_EQ(t5_2.timestamps.size(), 0);
 199   ASSERT_EQ(t5_4.timestamps.size(), 0);
 200   ASSERT_EQ(t5_5.timestamps.size(), 0);
 201   ASSERT_EQ(t10_2.timestamps.size(), 0);
 202   ASSERT_EQ(t20_1.timestamps.size(), 0);
 203   ASSERT_EQ(t20_2.timestamps.size(), 0);
 204
 205   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 206 }
 207
 208 /*
 209  * Test destroying a HHWheelTimer with timeouts outstanding
 210  */
 211
 212 TEST_F(HHWheelTimerTest, DestroyTimeoutSet) {
 213
 214   HHWheelTimer::UniquePtr t(
 215     new HHWheelTimer(&eventBase, milliseconds(1)));
 216
 217   TestTimeout t5_1(t.get(), milliseconds(5));
 218   TestTimeout t5_2(t.get(), milliseconds(5));
 219   TestTimeout t5_3(t.get(), milliseconds(5));
 220
 221   TestTimeout t10_1(t.get(), milliseconds(10));
 222   TestTimeout t10_2(t.get(), milliseconds(10));
 223
 224   // Have t5_2 destroy t
 225   // Note that this will call destroy() inside t's timeoutExpired()
 226   // method.
 227   t5_2.fn = [&] {
 228     t5_3.cancelTimeout();
 229     t5_1.cancelTimeout();
 230     t10_1.cancelTimeout();
 231     t10_2.cancelTimeout();
 232     t.reset();};
 233
 234   TimePoint start;
 235   eventBase.loop();
 236   TimePoint end;
 237
 238   ASSERT_EQ(t5_1.timestamps.size(), 1);
 239   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 240   ASSERT_EQ(t5_2.timestamps.size(), 1);
 241   T_CHECK_TIMEOUT(start, t5_2.timestamps[0], milliseconds(5));
 242
 243   ASSERT_EQ(t5_3.timestamps.size(), 0);
 244   ASSERT_EQ(t10_1.timestamps.size(), 0);
 245   ASSERT_EQ(t10_2.timestamps.size(), 0);
 246
 247   T_CHECK_TIMEOUT(start, end, milliseconds(5));
 248 }
 249
 250 /*
 251  * Test the tick interval parameter
 252  */
 253 TEST_F(HHWheelTimerTest, AtMostEveryN) {
 254
 255   // Create a timeout set with a 10ms interval, to fire no more than once
 256   // every 3ms.
 257   milliseconds interval(25);
 258   milliseconds atMostEveryN(6);
 259   StackWheelTimer t(&eventBase, atMostEveryN);
 260   t.setCatchupEveryN(70);
 261
 262   // Create 60 timeouts to be added to ts10 at 1ms intervals.
 263   uint32_t numTimeouts = 60;
 264   std::vector<TestTimeout> timeouts(numTimeouts);
 265
 266   // Create a scheduler timeout to add the timeouts 1ms apart.
 267   uint32_t index = 0;
 268   StackWheelTimer ts1(&eventBase, milliseconds(1));
 269   TestTimeout scheduler(&ts1, milliseconds(1));
 270   scheduler.fn = [&] {
 271     if (index >= numTimeouts) {
 272       return;
 273     }
 274     // Call timeoutExpired() on the timeout so it will record a timestamp.
 275     // This is done only so we can record when we scheduled the timeout.
 276     // This way if ts1 starts to fall behind a little over time we will still
 277     // be comparing the ts10 timeouts to when they were first scheduled (rather
 278     // than when we intended to schedule them).  The scheduler may fall behind
 279     // eventually since we don't really schedule it once every millisecond.
 280     // Each time it finishes we schedule it for 1 millisecond in the future.
 281     // The amount of time it takes to run, and any delays it encounters
 282     // getting scheduled may eventually add up over time.
 283     timeouts[index].timeoutExpired();
 284
 285     // Schedule the new timeout
 286     t.scheduleTimeout(&timeouts[index], interval);
 287     // Reschedule ourself
 288     ts1.scheduleTimeout(&scheduler, milliseconds(1));
 289     ++index;
 290   };
 291
 292   // Go ahead and schedule the first timeout now.
 293   //scheduler.fn();
 294
 295   TimePoint start;
 296   eventBase.loop();
 297   TimePoint end;
 298
 299   // We scheduled timeouts 1ms apart, when the HHWheelTimer is only allowed
 300   // to wake up at most once every 3ms.  It will therefore wake up every 3ms
 301   // and fire groups of approximately 3 timeouts at a time.
 302   //
 303   // This is "approximately 3" since it may get slightly behind and fire 4 in
 304   // one interval, etc.  T_CHECK_TIMEOUT normally allows a few milliseconds of
 305   // tolerance.  We have to add the same into our checking algorithm here.
 306   for (uint32_t idx = 0; idx < numTimeouts; ++idx) {
 307     ASSERT_EQ(timeouts[idx].timestamps.size(), 2);
 308
 309     TimePoint scheduledTime(timeouts[idx].timestamps[0]);
 310     TimePoint firedTime(timeouts[idx].timestamps[1]);
 311
 312     // Assert that the timeout fired at roughly the right time.
 313     // T_CHECK_TIMEOUT() normally has a tolerance of 5ms.  Allow an additional
 314     // atMostEveryN.
 315     milliseconds tolerance = milliseconds(5) + interval;
 316     T_CHECK_TIMEOUT(scheduledTime, firedTime, atMostEveryN, tolerance);
 317
 318     // Assert that the difference between the previous timeout and now was
 319     // either very small (fired in the same event loop), or larger than
 320     // atMostEveryN.
 321     if (idx == 0) {
 322       // no previous value
 323       continue;
 324     }
 325     TimePoint prev(timeouts[idx - 1].timestamps[1]);
 326
 327     auto delta = (firedTime.getTimeStart() - prev.getTimeEnd()) -
 328       (firedTime.getTimeWaiting() - prev.getTimeWaiting());
 329     if (delta > milliseconds(1)) {
 330       T_CHECK_TIMEOUT(prev, firedTime, atMostEveryN);
 331     }
 332   }
 333 }
 334
 335 /*
 336  * Test an event loop that is blocking
 337  */
 338
 339 TEST_F(HHWheelTimerTest, SlowLoop) {
 340   StackWheelTimer t(&eventBase, milliseconds(1));
 341
 342   TestTimeout t1;
 343   TestTimeout t2;
 344
 345   ASSERT_EQ(t.count(), 0);
 346
 347   eventBase.runInLoop([](){usleep(10000);});
 348   t.scheduleTimeout(&t1, milliseconds(5));
 349
 350   ASSERT_EQ(t.count(), 1);
 351
 352   TimePoint start;
 353   eventBase.loop();
 354   TimePoint end;
 355
 356   ASSERT_EQ(t1.timestamps.size(), 1);
 357   ASSERT_EQ(t.count(), 0);
 358
 359   // Check that the timeout was delayed by sleep
 360   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(15), milliseconds(1));
 361   T_CHECK_TIMEOUT(start, end, milliseconds(15), milliseconds(1));
 362
 363   // Try it again, this time with catchup timing every loop
 364   t.setCatchupEveryN(1);
 365
 366   eventBase.runInLoop([](){usleep(10000);});
 367   t.scheduleTimeout(&t2, milliseconds(5));
 368
 369   ASSERT_EQ(t.count(), 1);
 370
 371   TimePoint start2;
 372   eventBase.loop();
 373   TimePoint end2;
 374
 375   ASSERT_EQ(t2.timestamps.size(), 1);
 376   ASSERT_EQ(t.count(), 0);
 377
 378   // Check that the timeout was NOT delayed by sleep
 379   T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(10), milliseconds(1));
 380   T_CHECK_TIMEOUT(start2, end2, milliseconds(10), milliseconds(1));
 381 }
 382
 383 TEST_F(HHWheelTimerTest, lambda) {
 384   StackWheelTimer t(&eventBase, milliseconds(1));
 385   size_t count = 0;
 386   t.scheduleTimeoutFn([&]{ count++; }, milliseconds(1));
 387   eventBase.loop();
 388   EXPECT_EQ(1, count);
 389 }
 390
 391 // shouldn't crash because we swallow and log the error (you'll have to look
 392 // at the console to confirm logging)
 393 TEST_F(HHWheelTimerTest, lambdaThrows) {
 394   StackWheelTimer t(&eventBase, milliseconds(1));
 395   t.scheduleTimeoutFn([&]{ throw std::runtime_error("foo"); },
 396                       milliseconds(1));
 397   eventBase.loop();
 398 }