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 #include <folly/portability/GTest.h>
  24
  25 using namespace folly;
  26 using std::chrono::milliseconds;
  27
  28 typedef UndelayedDestruction<HHWheelTimer> StackWheelTimer;
  29
  30 class TestTimeout : public HHWheelTimer::Callback {
  31  public:
  32   TestTimeout() {}
  33   TestTimeout(HHWheelTimer* t, milliseconds timeout) {
  34     t->scheduleTimeout(this, timeout);
  35   }
  36
  37   void timeoutExpired() noexcept override {
  38     timestamps.emplace_back();
  39     if (fn) {
  40       fn();
  41     }
  42   }
  43
  44   void callbackCanceled() noexcept override {
  45     canceledTimestamps.emplace_back();
  46     if (fn) {
  47       fn();
  48     }
  49   }
  50
  51   std::deque<TimePoint> timestamps;
  52   std::deque<TimePoint> canceledTimestamps;
  53   std::function<void()> fn;
  54 };
  55
  56
  57 class TestTimeoutDelayed : public TestTimeout {
  58  protected:
  59     std::chrono::milliseconds getCurTime() override {
  60       return std::chrono::duration_cast<std::chrono::milliseconds>(
  61         std::chrono::steady_clock::now().time_since_epoch()) -
  62         milliseconds(5);
  63     }
  64 };
  65
  66 struct HHWheelTimerTest : public ::testing::Test {
  67   EventBase eventBase;
  68 };
  69
  70 /*
  71  * Test firing some simple timeouts that are fired once and never rescheduled
  72  */
  73 TEST_F(HHWheelTimerTest, FireOnce) {
  74   StackWheelTimer t(&eventBase, milliseconds(1));
  75
  76   TestTimeout t1;
  77   TestTimeout t2;
  78   TestTimeout t3;
  79
  80   ASSERT_EQ(t.count(), 0);
  81
  82   t.scheduleTimeout(&t1, milliseconds(5));
  83   t.scheduleTimeout(&t2, milliseconds(5));
  84   // Verify scheduling it twice cancels, then schedules.
  85   // Should only get one callback.
  86   t.scheduleTimeout(&t2, milliseconds(5));
  87   t.scheduleTimeout(&t3, milliseconds(10));
  88
  89   ASSERT_EQ(t.count(), 3);
  90
  91   TimePoint start;
  92   eventBase.loop();
  93   TimePoint end;
  94
  95   ASSERT_EQ(t1.timestamps.size(), 1);
  96   ASSERT_EQ(t2.timestamps.size(), 1);
  97   ASSERT_EQ(t3.timestamps.size(), 1);
  98
  99   ASSERT_EQ(t.count(), 0);
 100
 101   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
 102   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
 103   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
 104   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 105 }
 106
 107 /*
 108  * Test scheduling a timeout from another timeout callback.
 109  */
 110 TEST_F(HHWheelTimerTest, TestSchedulingWithinCallback) {
 111   HHWheelTimer& t = eventBase.timer();
 112
 113   TestTimeout t1;
 114   // Delayed to simulate the steady_clock counter lagging
 115   TestTimeoutDelayed t2;
 116
 117   t.scheduleTimeout(&t1, milliseconds(500));
 118   t1.fn = [&] { t.scheduleTimeout(&t2, milliseconds(1)); };
 119   // If t is in an inconsistent state, detachEventBase should fail.
 120   t2.fn = [&] { t.detachEventBase(); };
 121
 122   ASSERT_EQ(t.count(), 1);
 123
 124   eventBase.loop();
 125
 126   ASSERT_EQ(t.count(), 0);
 127   ASSERT_EQ(t1.timestamps.size(), 1);
 128   ASSERT_EQ(t2.timestamps.size(), 1);
 129 }
 130
 131 /*
 132  * Test cancelling a timeout when it is scheduled to be fired right away.
 133  */
 134
 135 TEST_F(HHWheelTimerTest, CancelTimeout) {
 136   StackWheelTimer t(&eventBase, milliseconds(1));
 137
 138   // Create several timeouts that will all fire in 5ms.
 139   TestTimeout t5_1(&t, milliseconds(5));
 140   TestTimeout t5_2(&t, milliseconds(5));
 141   TestTimeout t5_3(&t, milliseconds(5));
 142   TestTimeout t5_4(&t, milliseconds(5));
 143   TestTimeout t5_5(&t, milliseconds(5));
 144
 145   // Also create a few timeouts to fire in 10ms
 146   TestTimeout t10_1(&t, milliseconds(10));
 147   TestTimeout t10_2(&t, milliseconds(10));
 148   TestTimeout t10_3(&t, milliseconds(10));
 149
 150   TestTimeout t20_1(&t, milliseconds(20));
 151   TestTimeout t20_2(&t, milliseconds(20));
 152
 153   // Have t5_1 cancel t5_2 and t5_4.
 154   //
 155   // Cancelling t5_2 will test cancelling a timeout that is at the head of the
 156   // list and ready to be fired.
 157   //
 158   // Cancelling t5_4 will test cancelling a timeout in the middle of the list
 159   t5_1.fn = [&] {
 160     t5_2.cancelTimeout();
 161     t5_4.cancelTimeout();
 162   };
 163
 164   // Have t5_3 cancel t5_5.
 165   // This will test cancelling the last remaining timeout.
 166   //
 167   // Then have t5_3 reschedule itself.
 168   t5_3.fn = [&] {
 169     t5_5.cancelTimeout();
 170     // Reset our function so we won't continually reschedule ourself
 171     std::function<void()> fnDtorGuard;
 172     t5_3.fn.swap(fnDtorGuard);
 173     t.scheduleTimeout(&t5_3, milliseconds(5));
 174
 175     // Also test cancelling timeouts in another timeset that isn't ready to
 176     // fire yet.
 177     //
 178     // Cancel the middle timeout in ts10.
 179     t10_2.cancelTimeout();
 180     // Cancel both the timeouts in ts20.
 181     t20_1.cancelTimeout();
 182     t20_2.cancelTimeout();
 183   };
 184
 185   TimePoint start;
 186   eventBase.loop();
 187   TimePoint end;
 188
 189   ASSERT_EQ(t5_1.timestamps.size(), 1);
 190   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 191
 192   ASSERT_EQ(t5_3.timestamps.size(), 2);
 193   T_CHECK_TIMEOUT(start, t5_3.timestamps[0], milliseconds(5));
 194   T_CHECK_TIMEOUT(t5_3.timestamps[0], t5_3.timestamps[1], milliseconds(5));
 195
 196   ASSERT_EQ(t10_1.timestamps.size(), 1);
 197   T_CHECK_TIMEOUT(start, t10_1.timestamps[0], milliseconds(10));
 198   ASSERT_EQ(t10_3.timestamps.size(), 1);
 199   T_CHECK_TIMEOUT(start, t10_3.timestamps[0], milliseconds(10));
 200
 201   // Cancelled timeouts
 202   ASSERT_EQ(t5_2.timestamps.size(), 0);
 203   ASSERT_EQ(t5_4.timestamps.size(), 0);
 204   ASSERT_EQ(t5_5.timestamps.size(), 0);
 205   ASSERT_EQ(t10_2.timestamps.size(), 0);
 206   ASSERT_EQ(t20_1.timestamps.size(), 0);
 207   ASSERT_EQ(t20_2.timestamps.size(), 0);
 208
 209   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 210 }
 211
 212 /*
 213  * Test destroying a HHWheelTimer with timeouts outstanding
 214  */
 215
 216 TEST_F(HHWheelTimerTest, DestroyTimeoutSet) {
 217   HHWheelTimer::UniquePtr t(
 218       HHWheelTimer::newTimer(&eventBase, milliseconds(1)));
 219
 220   TestTimeout t5_1(t.get(), milliseconds(5));
 221   TestTimeout t5_2(t.get(), milliseconds(5));
 222   TestTimeout t5_3(t.get(), milliseconds(5));
 223
 224   TestTimeout t10_1(t.get(), milliseconds(10));
 225   TestTimeout t10_2(t.get(), milliseconds(10));
 226
 227   // Have t5_2 destroy t
 228   // Note that this will call destroy() inside t's timeoutExpired()
 229   // method.
 230   t5_2.fn = [&] {
 231     t5_3.cancelTimeout();
 232     t5_1.cancelTimeout();
 233     t10_1.cancelTimeout();
 234     t10_2.cancelTimeout();
 235     t.reset();};
 236
 237   TimePoint start;
 238   eventBase.loop();
 239   TimePoint end;
 240
 241   ASSERT_EQ(t5_1.timestamps.size(), 1);
 242   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 243   ASSERT_EQ(t5_2.timestamps.size(), 1);
 244   T_CHECK_TIMEOUT(start, t5_2.timestamps[0], milliseconds(5));
 245
 246   ASSERT_EQ(t5_3.timestamps.size(), 0);
 247   ASSERT_EQ(t10_1.timestamps.size(), 0);
 248   ASSERT_EQ(t10_2.timestamps.size(), 0);
 249
 250   T_CHECK_TIMEOUT(start, end, milliseconds(5));
 251 }
 252
 253 /*
 254  * Test an event scheduled before the last event fires on time
 255  */
 256
 257 TEST_F(HHWheelTimerTest, SlowFast) {
 258   StackWheelTimer t(&eventBase, milliseconds(1));
 259
 260   TestTimeout t1;
 261   TestTimeout t2;
 262
 263   ASSERT_EQ(t.count(), 0);
 264
 265   t.scheduleTimeout(&t1, milliseconds(10));
 266   t.scheduleTimeout(&t2, milliseconds(5));
 267
 268   ASSERT_EQ(t.count(), 2);
 269
 270   TimePoint start;
 271   eventBase.loop();
 272   TimePoint end;
 273
 274   ASSERT_EQ(t1.timestamps.size(), 1);
 275   ASSERT_EQ(t2.timestamps.size(), 1);
 276   ASSERT_EQ(t.count(), 0);
 277
 278   // Check that the timeout was delayed by sleep
 279   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(10), milliseconds(1));
 280   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5), milliseconds(1));
 281 }
 282
 283 TEST_F(HHWheelTimerTest, ReschedTest) {
 284   StackWheelTimer t(&eventBase, milliseconds(1));
 285
 286   TestTimeout t1;
 287   TestTimeout t2;
 288
 289   ASSERT_EQ(t.count(), 0);
 290
 291   t.scheduleTimeout(&t1, milliseconds(128));
 292   TimePoint start2;
 293   t1.fn = [&]() {
 294     t.scheduleTimeout(&t2, milliseconds(255)); // WHEEL_SIZE - 1
 295     start2.reset();
 296     ASSERT_EQ(t.count(), 1);
 297   };
 298
 299   ASSERT_EQ(t.count(), 1);
 300
 301   TimePoint start;
 302   eventBase.loop();
 303   TimePoint end;
 304
 305   ASSERT_EQ(t1.timestamps.size(), 1);
 306   ASSERT_EQ(t2.timestamps.size(), 1);
 307   ASSERT_EQ(t.count(), 0);
 308
 309   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
 310   T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(255), milliseconds(1));
 311 }
 312
 313 TEST_F(HHWheelTimerTest, DeleteWheelInTimeout) {
 314   auto t = HHWheelTimer::newTimer(&eventBase, milliseconds(1));
 315
 316   TestTimeout t1;
 317   TestTimeout t2;
 318   TestTimeout t3;
 319
 320   ASSERT_EQ(t->count(), 0);
 321
 322   t->scheduleTimeout(&t1, milliseconds(128));
 323   t->scheduleTimeout(&t2, milliseconds(128));
 324   t->scheduleTimeout(&t3, milliseconds(128));
 325   t1.fn = [&]() { t2.cancelTimeout(); };
 326   t3.fn = [&]() { t.reset(); };
 327
 328   ASSERT_EQ(t->count(), 3);
 329
 330   TimePoint start;
 331   eventBase.loop();
 332   TimePoint end;
 333
 334   ASSERT_EQ(t1.timestamps.size(), 1);
 335   ASSERT_EQ(t2.timestamps.size(), 0);
 336
 337   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
 338 }
 339
 340 /*
 341  * Test scheduling a mix of timers with default timeout and variable timeout.
 342  */
 343 TEST_F(HHWheelTimerTest, DefaultTimeout) {
 344   milliseconds defaultTimeout(milliseconds(5));
 345   StackWheelTimer t(&eventBase,
 346                     milliseconds(1),
 347                     AsyncTimeout::InternalEnum::NORMAL,
 348                     defaultTimeout);
 349
 350   TestTimeout t1;
 351   TestTimeout t2;
 352
 353   ASSERT_EQ(t.count(), 0);
 354   ASSERT_EQ(t.getDefaultTimeout(), defaultTimeout);
 355
 356   t.scheduleTimeout(&t1);
 357   t.scheduleTimeout(&t2, milliseconds(10));
 358
 359   ASSERT_EQ(t.count(), 2);
 360
 361   TimePoint start;
 362   eventBase.loop();
 363   TimePoint end;
 364
 365   ASSERT_EQ(t1.timestamps.size(), 1);
 366   ASSERT_EQ(t2.timestamps.size(), 1);
 367
 368   ASSERT_EQ(t.count(), 0);
 369
 370   T_CHECK_TIMEOUT(start, t1.timestamps[0], defaultTimeout);
 371   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(10));
 372   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 373 }
 374
 375 TEST_F(HHWheelTimerTest, lambda) {
 376   StackWheelTimer t(&eventBase, milliseconds(1));
 377   size_t count = 0;
 378   t.scheduleTimeoutFn([&]{ count++; }, milliseconds(1));
 379   eventBase.loop();
 380   EXPECT_EQ(1, count);
 381 }
 382
 383 // shouldn't crash because we swallow and log the error (you'll have to look
 384 // at the console to confirm logging)
 385 TEST_F(HHWheelTimerTest, lambdaThrows) {
 386   StackWheelTimer t(&eventBase, milliseconds(1));
 387   t.scheduleTimeoutFn([&]{ throw std::runtime_error("expected"); },
 388                       milliseconds(1));
 389   eventBase.loop();
 390 }
 391
 392 TEST_F(HHWheelTimerTest, cancelAll) {
 393   StackWheelTimer t(&eventBase, milliseconds(1));
 394   TestTimeout tt;
 395   t.scheduleTimeout(&tt, std::chrono::minutes(1));
 396   EXPECT_EQ(1, t.cancelAll());
 397   EXPECT_EQ(1, tt.canceledTimestamps.size());
 398 }
 399
 400 TEST_F(HHWheelTimerTest, IntrusivePtr) {
 401   HHWheelTimer::UniquePtr t(
 402       HHWheelTimer::newTimer(&eventBase, milliseconds(1)));
 403
 404   TestTimeout t1;
 405   TestTimeout t2;
 406   TestTimeout t3;
 407
 408   ASSERT_EQ(t->count(), 0);
 409
 410   t->scheduleTimeout(&t1, milliseconds(5));
 411   t->scheduleTimeout(&t2, milliseconds(5));
 412
 413   DelayedDestruction::IntrusivePtr<HHWheelTimer> s(t);
 414
 415   s->scheduleTimeout(&t3, milliseconds(10));
 416
 417   ASSERT_EQ(t->count(), 3);
 418
 419   // Kill the UniquePtr, but the SharedPtr keeps it alive
 420   t.reset();
 421
 422   TimePoint start;
 423   eventBase.loop();
 424   TimePoint end;
 425
 426   ASSERT_EQ(t1.timestamps.size(), 1);
 427   ASSERT_EQ(t2.timestamps.size(), 1);
 428   ASSERT_EQ(t3.timestamps.size(), 1);
 429
 430   ASSERT_EQ(s->count(), 0);
 431
 432   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
 433   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
 434   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
 435   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 436 }