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 /*
  60  * Test firing some simple timeouts that are fired once and never rescheduled
  61  */
  62 TEST(HHWheelTimerTest, FireOnce) {
  63   EventBase eventBase;
  64   StackWheelTimer t(&eventBase, milliseconds(1));
  65
  66   const HHWheelTimer::Callback* nullCallback = nullptr;
  67
  68   TestTimeout t1;
  69   TestTimeout t2;
  70   TestTimeout t3;
  71
  72   ASSERT_EQ(t.count(), 0);
  73
  74   t.scheduleTimeout(&t1, milliseconds(5));
  75   t.scheduleTimeout(&t2, milliseconds(5));
  76   // Verify scheduling it twice cancels, then schedules.
  77   // Should only get one callback.
  78   t.scheduleTimeout(&t2, milliseconds(5));
  79   t.scheduleTimeout(&t3, milliseconds(10));
  80
  81   ASSERT_EQ(t.count(), 3);
  82
  83   TimePoint start;
  84   eventBase.loop();
  85   TimePoint end;
  86
  87   ASSERT_EQ(t1.timestamps.size(), 1);
  88   ASSERT_EQ(t2.timestamps.size(), 1);
  89   ASSERT_EQ(t3.timestamps.size(), 1);
  90
  91   ASSERT_EQ(t.count(), 0);
  92
  93   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
  94   T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
  95   T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
  96   T_CHECK_TIMEOUT(start, end, milliseconds(10));
  97 }
  98
  99 /*
 100  * Test scheduling a timeout from another timeout callback.
 101  */
 102 TEST(HHWheelTimerTest, TestSchedulingWithinCallback) {
 103   EventBase eventBase;
 104   StackWheelTimer t(&eventBase, milliseconds(10));
 105   const HHWheelTimer::Callback* nullCallback = nullptr;
 106
 107   TestTimeout t1;
 108   // Delayed to simulate the steady_clock counter lagging
 109   TestTimeoutDelayed t2;
 110
 111   t.scheduleTimeout(&t1, milliseconds(500));
 112   t1.fn = [&] { t.scheduleTimeout(&t2, milliseconds(1)); };
 113   // If t is in an inconsistent state, detachEventBase should fail.
 114   t2.fn = [&] { t.detachEventBase(); };
 115
 116   ASSERT_EQ(t.count(), 1);
 117
 118   eventBase.loop();
 119
 120   ASSERT_EQ(t.count(), 0);
 121   ASSERT_EQ(t1.timestamps.size(), 1);
 122   ASSERT_EQ(t2.timestamps.size(), 1);
 123 }
 124
 125 /*
 126  * Test cancelling a timeout when it is scheduled to be fired right away.
 127  */
 128
 129 TEST(HHWheelTimerTest, CancelTimeout) {
 130   EventBase eventBase;
 131   StackWheelTimer t(&eventBase, milliseconds(1));
 132
 133   // Create several timeouts that will all fire in 5ms.
 134   TestTimeout t5_1(&t, milliseconds(5));
 135   TestTimeout t5_2(&t, milliseconds(5));
 136   TestTimeout t5_3(&t, milliseconds(5));
 137   TestTimeout t5_4(&t, milliseconds(5));
 138   TestTimeout t5_5(&t, milliseconds(5));
 139
 140   // Also create a few timeouts to fire in 10ms
 141   TestTimeout t10_1(&t, milliseconds(10));
 142   TestTimeout t10_2(&t, milliseconds(10));
 143   TestTimeout t10_3(&t, milliseconds(10));
 144
 145   TestTimeout t20_1(&t, milliseconds(20));
 146   TestTimeout t20_2(&t, milliseconds(20));
 147
 148   // Have t5_1 cancel t5_2 and t5_4.
 149   //
 150   // Cancelling t5_2 will test cancelling a timeout that is at the head of the
 151   // list and ready to be fired.
 152   //
 153   // Cancelling t5_4 will test cancelling a timeout in the middle of the list
 154   t5_1.fn = [&] {
 155     t5_2.cancelTimeout();
 156     t5_4.cancelTimeout();
 157   };
 158
 159   // Have t5_3 cancel t5_5.
 160   // This will test cancelling the last remaining timeout.
 161   //
 162   // Then have t5_3 reschedule itself.
 163   t5_3.fn = [&] {
 164     t5_5.cancelTimeout();
 165     // Reset our function so we won't continually reschedule ourself
 166     std::function<void()> fnDtorGuard;
 167     t5_3.fn.swap(fnDtorGuard);
 168     t.scheduleTimeout(&t5_3, milliseconds(5));
 169
 170     // Also test cancelling timeouts in another timeset that isn't ready to
 171     // fire yet.
 172     //
 173     // Cancel the middle timeout in ts10.
 174     t10_2.cancelTimeout();
 175     // Cancel both the timeouts in ts20.
 176     t20_1.cancelTimeout();
 177     t20_2.cancelTimeout();
 178   };
 179
 180   TimePoint start;
 181   eventBase.loop();
 182   TimePoint end;
 183
 184   ASSERT_EQ(t5_1.timestamps.size(), 1);
 185   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 186
 187   ASSERT_EQ(t5_3.timestamps.size(), 2);
 188   T_CHECK_TIMEOUT(start, t5_3.timestamps[0], milliseconds(5));
 189   T_CHECK_TIMEOUT(t5_3.timestamps[0], t5_3.timestamps[1], milliseconds(5));
 190
 191   ASSERT_EQ(t10_1.timestamps.size(), 1);
 192   T_CHECK_TIMEOUT(start, t10_1.timestamps[0], milliseconds(10));
 193   ASSERT_EQ(t10_3.timestamps.size(), 1);
 194   T_CHECK_TIMEOUT(start, t10_3.timestamps[0], milliseconds(10));
 195
 196   // Cancelled timeouts
 197   ASSERT_EQ(t5_2.timestamps.size(), 0);
 198   ASSERT_EQ(t5_4.timestamps.size(), 0);
 199   ASSERT_EQ(t5_5.timestamps.size(), 0);
 200   ASSERT_EQ(t10_2.timestamps.size(), 0);
 201   ASSERT_EQ(t20_1.timestamps.size(), 0);
 202   ASSERT_EQ(t20_2.timestamps.size(), 0);
 203
 204   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 205 }
 206
 207 /*
 208  * Test destroying a HHWheelTimer with timeouts outstanding
 209  */
 210
 211 TEST(HHWheelTimerTest, DestroyTimeoutSet) {
 212   EventBase eventBase;
 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(HHWheelTimerTest, AtMostEveryN) {
 254   EventBase eventBase;
 255
 256   // Create a timeout set with a 10ms interval, to fire no more than once
 257   // every 3ms.
 258   milliseconds interval(25);
 259   milliseconds atMostEveryN(6);
 260   StackWheelTimer t(&eventBase, atMostEveryN);
 261   t.setCatchupEveryN(70);
 262
 263   // Create 60 timeouts to be added to ts10 at 1ms intervals.
 264   uint32_t numTimeouts = 60;
 265   std::vector<TestTimeout> timeouts(numTimeouts);
 266
 267   // Create a scheduler timeout to add the timeouts 1ms apart.
 268   uint32_t index = 0;
 269   StackWheelTimer ts1(&eventBase, milliseconds(1));
 270   TestTimeout scheduler(&ts1, milliseconds(1));
 271   scheduler.fn = [&] {
 272     if (index >= numTimeouts) {
 273       return;
 274     }
 275     // Call timeoutExpired() on the timeout so it will record a timestamp.
 276     // This is done only so we can record when we scheduled the timeout.
 277     // This way if ts1 starts to fall behind a little over time we will still
 278     // be comparing the ts10 timeouts to when they were first scheduled (rather
 279     // than when we intended to schedule them).  The scheduler may fall behind
 280     // eventually since we don't really schedule it once every millisecond.
 281     // Each time it finishes we schedule it for 1 millisecond in the future.
 282     // The amount of time it takes to run, and any delays it encounters
 283     // getting scheduled may eventually add up over time.
 284     timeouts[index].timeoutExpired();
 285
 286     // Schedule the new timeout
 287     t.scheduleTimeout(&timeouts[index], interval);
 288     // Reschedule ourself
 289     ts1.scheduleTimeout(&scheduler, milliseconds(1));
 290     ++index;
 291   };
 292
 293   // Go ahead and schedule the first timeout now.
 294   //scheduler.fn();
 295
 296   TimePoint start;
 297   eventBase.loop();
 298   TimePoint end;
 299
 300   // We scheduled timeouts 1ms apart, when the HHWheelTimer is only allowed
 301   // to wake up at most once every 3ms.  It will therefore wake up every 3ms
 302   // and fire groups of approximately 3 timeouts at a time.
 303   //
 304   // This is "approximately 3" since it may get slightly behind and fire 4 in
 305   // one interval, etc.  T_CHECK_TIMEOUT normally allows a few milliseconds of
 306   // tolerance.  We have to add the same into our checking algorithm here.
 307   for (uint32_t idx = 0; idx < numTimeouts; ++idx) {
 308     ASSERT_EQ(timeouts[idx].timestamps.size(), 2);
 309
 310     TimePoint scheduledTime(timeouts[idx].timestamps[0]);
 311     TimePoint firedTime(timeouts[idx].timestamps[1]);
 312
 313     // Assert that the timeout fired at roughly the right time.
 314     // T_CHECK_TIMEOUT() normally has a tolerance of 5ms.  Allow an additional
 315     // atMostEveryN.
 316     milliseconds tolerance = milliseconds(5) + interval;
 317     T_CHECK_TIMEOUT(scheduledTime, firedTime, atMostEveryN, tolerance);
 318
 319     // Assert that the difference between the previous timeout and now was
 320     // either very small (fired in the same event loop), or larger than
 321     // atMostEveryN.
 322     if (idx == 0) {
 323       // no previous value
 324       continue;
 325     }
 326     TimePoint prev(timeouts[idx - 1].timestamps[1]);
 327
 328     auto delta = (firedTime.getTimeStart() - prev.getTimeEnd()) -
 329       (firedTime.getTimeWaiting() - prev.getTimeWaiting());
 330     if (delta > milliseconds(1)) {
 331       T_CHECK_TIMEOUT(prev, firedTime, atMostEveryN);
 332     }
 333   }
 334 }
 335
 336 /*
 337  * Test an event loop that is blocking
 338  */
 339
 340 TEST(HHWheelTimerTest, SlowLoop) {
 341   EventBase eventBase;
 342   StackWheelTimer t(&eventBase, milliseconds(1));
 343
 344   TestTimeout t1;
 345   TestTimeout t2;
 346
 347   ASSERT_EQ(t.count(), 0);
 348
 349   eventBase.runInLoop([](){usleep(10000);});
 350   t.scheduleTimeout(&t1, milliseconds(5));
 351
 352   ASSERT_EQ(t.count(), 1);
 353
 354   TimePoint start;
 355   eventBase.loop();
 356   TimePoint end;
 357
 358   ASSERT_EQ(t1.timestamps.size(), 1);
 359   ASSERT_EQ(t.count(), 0);
 360
 361   // Check that the timeout was delayed by sleep
 362   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(15), milliseconds(1));
 363   T_CHECK_TIMEOUT(start, end, milliseconds(15), milliseconds(1));
 364
 365   // Try it again, this time with catchup timing every loop
 366   t.setCatchupEveryN(1);
 367
 368   eventBase.runInLoop([](){usleep(10000);});
 369   t.scheduleTimeout(&t2, milliseconds(5));
 370
 371   ASSERT_EQ(t.count(), 1);
 372
 373   TimePoint start2;
 374   eventBase.loop();
 375   TimePoint end2;
 376
 377   ASSERT_EQ(t2.timestamps.size(), 1);
 378   ASSERT_EQ(t.count(), 0);
 379
 380   // Check that the timeout was NOT delayed by sleep
 381   T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(10), milliseconds(1));
 382   T_CHECK_TIMEOUT(start2, end2, milliseconds(10), milliseconds(1));
 383 }