folly/io/async/test/HHWheelTimerTest.cpp

   1 /*
   2  * Copyright 2004-present 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
  17 #include <folly/io/async/HHWheelTimer.h>
  18 #include <folly/io/async/EventBase.h>
  19 #include <folly/io/async/test/UndelayedDestruction.h>
  20 #include <folly/io/async/test/Util.h>
  21 #include <folly/portability/GTest.h>
  22
  23 using namespace folly;
  24 using std::chrono::milliseconds;
  25
  26 typedef UndelayedDestruction<HHWheelTimer> StackWheelTimer;
  27
  28 class TestTimeout : public HHWheelTimer::Callback {
  29  public:
  30   TestTimeout() {}
  31   TestTimeout(HHWheelTimer* t, milliseconds timeout) {
  32     t->scheduleTimeout(this, timeout);
  33   }
  34
  35   void timeoutExpired() noexcept override {
  36     timestamps.emplace_back();
  37     if (fn) {
  38       fn();
  39     }
  40   }
  41
  42   void callbackCanceled() noexcept override {
  43     canceledTimestamps.emplace_back();
  44     if (fn) {
  45       fn();
  46     }
  47   }
  48
  49   std::deque<TimePoint> timestamps;
  50   std::deque<TimePoint> canceledTimestamps;
  51   std::function<void()> fn;
  52 };
  53
  54
  55 class TestTimeoutDelayed : public TestTimeout {
  56  protected:
  57   std::chrono::steady_clock::time_point getCurTime() override {
  58     return std::chrono::steady_clock::now() - milliseconds(5);
  59   }
  60 };
  61
  62 struct HHWheelTimerTest : public ::testing::Test {
  63   EventBase eventBase;
  64 };
  65
  66 /*
  67  * Test firing some simple timeouts that are fired once and never rescheduled
  68  */
  69 TEST_F(HHWheelTimerTest, FireOnce) {
  70   StackWheelTimer t(&eventBase, milliseconds(1));
  71
  72   TestTimeout t1;
  73   TestTimeout t2;
  74   TestTimeout t3;
  75
  76   ASSERT_EQ(t.count(), 0);
  77
  78   t.scheduleTimeout(&t1, milliseconds(5));
  79   t.scheduleTimeout(&t2, milliseconds(5));
  80   // Verify scheduling it twice cancels, then schedules.
  81   // Should only get one callback.
  82   t.scheduleTimeout(&t2, milliseconds(5));
  83   t.scheduleTimeout(&t3, milliseconds(10));
  84
  85   ASSERT_EQ(t.count(), 3);
  86
  87   TimePoint start;
  88   eventBase.loop();
  89   TimePoint end;
  90
  91   ASSERT_EQ(t1.timestamps.size(), 1);
  92   ASSERT_EQ(t2.timestamps.size(), 1);
  93   ASSERT_EQ(t3.timestamps.size(), 1);
  94
  95   ASSERT_EQ(t.count(), 0);
  96
  97   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
  98   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
  99   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
 100   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 101 }
 102
 103 /*
 104  * Test scheduling a timeout from another timeout callback.
 105  */
 106 TEST_F(HHWheelTimerTest, TestSchedulingWithinCallback) {
 107   HHWheelTimer& t = eventBase.timer();
 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   HHWheelTimer::UniquePtr t(
 214       HHWheelTimer::newTimer(&eventBase, milliseconds(1)));
 215
 216   TestTimeout t5_1(t.get(), milliseconds(5));
 217   TestTimeout t5_2(t.get(), milliseconds(5));
 218   TestTimeout t5_3(t.get(), milliseconds(5));
 219
 220   TestTimeout t10_1(t.get(), milliseconds(10));
 221   TestTimeout t10_2(t.get(), milliseconds(10));
 222
 223   // Have t5_2 destroy t
 224   // Note that this will call destroy() inside t's timeoutExpired()
 225   // method.
 226   t5_2.fn = [&] {
 227     t5_3.cancelTimeout();
 228     t5_1.cancelTimeout();
 229     t10_1.cancelTimeout();
 230     t10_2.cancelTimeout();
 231     t.reset();};
 232
 233   TimePoint start;
 234   eventBase.loop();
 235   TimePoint end;
 236
 237   ASSERT_EQ(t5_1.timestamps.size(), 1);
 238   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 239   ASSERT_EQ(t5_2.timestamps.size(), 1);
 240   T_CHECK_TIMEOUT(start, t5_2.timestamps[0], milliseconds(5));
 241
 242   ASSERT_EQ(t5_3.timestamps.size(), 0);
 243   ASSERT_EQ(t10_1.timestamps.size(), 0);
 244   ASSERT_EQ(t10_2.timestamps.size(), 0);
 245
 246   T_CHECK_TIMEOUT(start, end, milliseconds(5));
 247 }
 248
 249 /*
 250  * Test an event scheduled before the last event fires on time
 251  */
 252
 253 TEST_F(HHWheelTimerTest, SlowFast) {
 254   StackWheelTimer t(&eventBase, milliseconds(1));
 255
 256   TestTimeout t1;
 257   TestTimeout t2;
 258
 259   ASSERT_EQ(t.count(), 0);
 260
 261   t.scheduleTimeout(&t1, milliseconds(10));
 262   t.scheduleTimeout(&t2, milliseconds(5));
 263
 264   ASSERT_EQ(t.count(), 2);
 265
 266   TimePoint start;
 267   eventBase.loop();
 268   TimePoint end;
 269
 270   ASSERT_EQ(t1.timestamps.size(), 1);
 271   ASSERT_EQ(t2.timestamps.size(), 1);
 272   ASSERT_EQ(t.count(), 0);
 273
 274   // Check that the timeout was delayed by sleep
 275   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(10), milliseconds(1));
 276   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5), milliseconds(1));
 277 }
 278
 279 TEST_F(HHWheelTimerTest, ReschedTest) {
 280   StackWheelTimer t(&eventBase, milliseconds(1));
 281
 282   TestTimeout t1;
 283   TestTimeout t2;
 284
 285   ASSERT_EQ(t.count(), 0);
 286
 287   t.scheduleTimeout(&t1, milliseconds(128));
 288   TimePoint start2;
 289   t1.fn = [&]() {
 290     t.scheduleTimeout(&t2, milliseconds(255)); // WHEEL_SIZE - 1
 291     start2.reset();
 292     ASSERT_EQ(t.count(), 1);
 293   };
 294
 295   ASSERT_EQ(t.count(), 1);
 296
 297   TimePoint start;
 298   eventBase.loop();
 299   TimePoint end;
 300
 301   ASSERT_EQ(t1.timestamps.size(), 1);
 302   ASSERT_EQ(t2.timestamps.size(), 1);
 303   ASSERT_EQ(t.count(), 0);
 304
 305   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
 306   T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(255), milliseconds(1));
 307 }
 308
 309 TEST_F(HHWheelTimerTest, DeleteWheelInTimeout) {
 310   auto t = HHWheelTimer::newTimer(&eventBase, milliseconds(1));
 311
 312   TestTimeout t1;
 313   TestTimeout t2;
 314   TestTimeout t3;
 315
 316   ASSERT_EQ(t->count(), 0);
 317
 318   t->scheduleTimeout(&t1, milliseconds(128));
 319   t->scheduleTimeout(&t2, milliseconds(128));
 320   t->scheduleTimeout(&t3, milliseconds(128));
 321   t1.fn = [&]() { t2.cancelTimeout(); };
 322   t3.fn = [&]() { t.reset(); };
 323
 324   ASSERT_EQ(t->count(), 3);
 325
 326   TimePoint start;
 327   eventBase.loop();
 328   TimePoint end;
 329
 330   ASSERT_EQ(t1.timestamps.size(), 1);
 331   ASSERT_EQ(t2.timestamps.size(), 0);
 332
 333   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
 334 }
 335
 336 /*
 337  * Test scheduling a mix of timers with default timeout and variable timeout.
 338  */
 339 TEST_F(HHWheelTimerTest, DefaultTimeout) {
 340   milliseconds defaultTimeout(milliseconds(5));
 341   StackWheelTimer t(&eventBase,
 342                     milliseconds(1),
 343                     AsyncTimeout::InternalEnum::NORMAL,
 344                     defaultTimeout);
 345
 346   TestTimeout t1;
 347   TestTimeout t2;
 348
 349   ASSERT_EQ(t.count(), 0);
 350   ASSERT_EQ(t.getDefaultTimeout(), defaultTimeout);
 351
 352   t.scheduleTimeout(&t1);
 353   t.scheduleTimeout(&t2, milliseconds(10));
 354
 355   ASSERT_EQ(t.count(), 2);
 356
 357   TimePoint start;
 358   eventBase.loop();
 359   TimePoint end;
 360
 361   ASSERT_EQ(t1.timestamps.size(), 1);
 362   ASSERT_EQ(t2.timestamps.size(), 1);
 363
 364   ASSERT_EQ(t.count(), 0);
 365
 366   T_CHECK_TIMEOUT(start, t1.timestamps[0], defaultTimeout);
 367   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(10));
 368   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 369 }
 370
 371 TEST_F(HHWheelTimerTest, lambda) {
 372   StackWheelTimer t(&eventBase, milliseconds(1));
 373   size_t count = 0;
 374   t.scheduleTimeoutFn([&]{ count++; }, milliseconds(1));
 375   eventBase.loop();
 376   EXPECT_EQ(1, count);
 377 }
 378
 379 // shouldn't crash because we swallow and log the error (you'll have to look
 380 // at the console to confirm logging)
 381 TEST_F(HHWheelTimerTest, lambdaThrows) {
 382   StackWheelTimer t(&eventBase, milliseconds(1));
 383   t.scheduleTimeoutFn([&]{ throw std::runtime_error("expected"); },
 384                       milliseconds(1));
 385   eventBase.loop();
 386 }
 387
 388 TEST_F(HHWheelTimerTest, cancelAll) {
 389   StackWheelTimer t(&eventBase, milliseconds(1));
 390   TestTimeout tt;
 391   t.scheduleTimeout(&tt, std::chrono::minutes(1));
 392   EXPECT_EQ(1, t.cancelAll());
 393   EXPECT_EQ(1, tt.canceledTimestamps.size());
 394 }
 395
 396 TEST_F(HHWheelTimerTest, IntrusivePtr) {
 397   HHWheelTimer::UniquePtr t(
 398       HHWheelTimer::newTimer(&eventBase, milliseconds(1)));
 399
 400   TestTimeout t1;
 401   TestTimeout t2;
 402   TestTimeout t3;
 403
 404   ASSERT_EQ(t->count(), 0);
 405
 406   t->scheduleTimeout(&t1, milliseconds(5));
 407   t->scheduleTimeout(&t2, milliseconds(5));
 408
 409   DelayedDestruction::IntrusivePtr<HHWheelTimer> s(t);
 410
 411   s->scheduleTimeout(&t3, milliseconds(10));
 412
 413   ASSERT_EQ(t->count(), 3);
 414
 415   // Kill the UniquePtr, but the SharedPtr keeps it alive
 416   t.reset();
 417
 418   TimePoint start;
 419   eventBase.loop();
 420   TimePoint end;
 421
 422   ASSERT_EQ(t1.timestamps.size(), 1);
 423   ASSERT_EQ(t2.timestamps.size(), 1);
 424   ASSERT_EQ(t3.timestamps.size(), 1);
 425
 426   ASSERT_EQ(s->count(), 0);
 427
 428   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
 429   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
 430   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
 431   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 432 }