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