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 cancelling a timeout when it is scheduled to be fired right away.
 101  */
 102
 103 TEST(HHWheelTimerTest, CancelTimeout) {
 104   EventBase eventBase;
 105   StackWheelTimer t(&eventBase, milliseconds(1));
 106
 107   // Create several timeouts that will all fire in 5ms.
 108   TestTimeout t5_1(&t, milliseconds(5));
 109   TestTimeout t5_2(&t, milliseconds(5));
 110   TestTimeout t5_3(&t, milliseconds(5));
 111   TestTimeout t5_4(&t, milliseconds(5));
 112   TestTimeout t5_5(&t, milliseconds(5));
 113
 114   // Also create a few timeouts to fire in 10ms
 115   TestTimeout t10_1(&t, milliseconds(10));
 116   TestTimeout t10_2(&t, milliseconds(10));
 117   TestTimeout t10_3(&t, milliseconds(10));
 118
 119   TestTimeout t20_1(&t, milliseconds(20));
 120   TestTimeout t20_2(&t, milliseconds(20));
 121
 122   // Have t5_1 cancel t5_2 and t5_4.
 123   //
 124   // Cancelling t5_2 will test cancelling a timeout that is at the head of the
 125   // list and ready to be fired.
 126   //
 127   // Cancelling t5_4 will test cancelling a timeout in the middle of the list
 128   t5_1.fn = [&] {
 129     t5_2.cancelTimeout();
 130     t5_4.cancelTimeout();
 131   };
 132
 133   // Have t5_3 cancel t5_5.
 134   // This will test cancelling the last remaining timeout.
 135   //
 136   // Then have t5_3 reschedule itself.
 137   t5_3.fn = [&] {
 138     t5_5.cancelTimeout();
 139     // Reset our function so we won't continually reschedule ourself
 140     std::function<void()> fnDtorGuard;
 141     t5_3.fn.swap(fnDtorGuard);
 142     t.scheduleTimeout(&t5_3, milliseconds(5));
 143
 144     // Also test cancelling timeouts in another timeset that isn't ready to
 145     // fire yet.
 146     //
 147     // Cancel the middle timeout in ts10.
 148     t10_2.cancelTimeout();
 149     // Cancel both the timeouts in ts20.
 150     t20_1.cancelTimeout();
 151     t20_2.cancelTimeout();
 152   };
 153
 154   TimePoint start;
 155   eventBase.loop();
 156   TimePoint end;
 157
 158   ASSERT_EQ(t5_1.timestamps.size(), 1);
 159   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 160
 161   ASSERT_EQ(t5_3.timestamps.size(), 2);
 162   T_CHECK_TIMEOUT(start, t5_3.timestamps[0], milliseconds(5));
 163   T_CHECK_TIMEOUT(t5_3.timestamps[0], t5_3.timestamps[1], milliseconds(5));
 164
 165   ASSERT_EQ(t10_1.timestamps.size(), 1);
 166   T_CHECK_TIMEOUT(start, t10_1.timestamps[0], milliseconds(10));
 167   ASSERT_EQ(t10_3.timestamps.size(), 1);
 168   T_CHECK_TIMEOUT(start, t10_3.timestamps[0], milliseconds(10));
 169
 170   // Cancelled timeouts
 171   ASSERT_EQ(t5_2.timestamps.size(), 0);
 172   ASSERT_EQ(t5_4.timestamps.size(), 0);
 173   ASSERT_EQ(t5_5.timestamps.size(), 0);
 174   ASSERT_EQ(t10_2.timestamps.size(), 0);
 175   ASSERT_EQ(t20_1.timestamps.size(), 0);
 176   ASSERT_EQ(t20_2.timestamps.size(), 0);
 177
 178   T_CHECK_TIMEOUT(start, end, milliseconds(10));
 179 }
 180
 181 /*
 182  * Test destroying a HHWheelTimer with timeouts outstanding
 183  */
 184
 185 TEST(HHWheelTimerTest, DestroyTimeoutSet) {
 186   EventBase eventBase;
 187
 188   HHWheelTimer::UniquePtr t(
 189     new HHWheelTimer(&eventBase, milliseconds(1)));
 190
 191   TestTimeout t5_1(t.get(), milliseconds(5));
 192   TestTimeout t5_2(t.get(), milliseconds(5));
 193   TestTimeout t5_3(t.get(), milliseconds(5));
 194
 195   TestTimeout t10_1(t.get(), milliseconds(10));
 196   TestTimeout t10_2(t.get(), milliseconds(10));
 197
 198   // Have t5_2 destroy t
 199   // Note that this will call destroy() inside t's timeoutExpired()
 200   // method.
 201   t5_2.fn = [&] {
 202     t5_3.cancelTimeout();
 203     t5_1.cancelTimeout();
 204     t10_1.cancelTimeout();
 205     t10_2.cancelTimeout();
 206     t.reset();};
 207
 208   TimePoint start;
 209   eventBase.loop();
 210   TimePoint end;
 211
 212   ASSERT_EQ(t5_1.timestamps.size(), 1);
 213   T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
 214   ASSERT_EQ(t5_2.timestamps.size(), 1);
 215   T_CHECK_TIMEOUT(start, t5_2.timestamps[0], milliseconds(5));
 216
 217   ASSERT_EQ(t5_3.timestamps.size(), 0);
 218   ASSERT_EQ(t10_1.timestamps.size(), 0);
 219   ASSERT_EQ(t10_2.timestamps.size(), 0);
 220
 221   T_CHECK_TIMEOUT(start, end, milliseconds(5));
 222 }
 223
 224 /*
 225  * Test the tick interval parameter
 226  */
 227 TEST(HHWheelTimerTest, AtMostEveryN) {
 228   EventBase eventBase;
 229
 230   // Create a timeout set with a 10ms interval, to fire no more than once
 231   // every 3ms.
 232   milliseconds interval(25);
 233   milliseconds atMostEveryN(6);
 234   StackWheelTimer t(&eventBase, atMostEveryN);
 235   t.setCatchupEveryN(70);
 236
 237   // Create 60 timeouts to be added to ts10 at 1ms intervals.
 238   uint32_t numTimeouts = 60;
 239   std::vector<TestTimeout> timeouts(numTimeouts);
 240
 241   // Create a scheduler timeout to add the timeouts 1ms apart.
 242   uint32_t index = 0;
 243   StackWheelTimer ts1(&eventBase, milliseconds(1));
 244   TestTimeout scheduler(&ts1, milliseconds(1));
 245   scheduler.fn = [&] {
 246     if (index >= numTimeouts) {
 247       return;
 248     }
 249     // Call timeoutExpired() on the timeout so it will record a timestamp.
 250     // This is done only so we can record when we scheduled the timeout.
 251     // This way if ts1 starts to fall behind a little over time we will still
 252     // be comparing the ts10 timeouts to when they were first scheduled (rather
 253     // than when we intended to schedule them).  The scheduler may fall behind
 254     // eventually since we don't really schedule it once every millisecond.
 255     // Each time it finishes we schedule it for 1 millisecond in the future.
 256     // The amount of time it takes to run, and any delays it encounters
 257     // getting scheduled may eventually add up over time.
 258     timeouts[index].timeoutExpired();
 259
 260     // Schedule the new timeout
 261     t.scheduleTimeout(&timeouts[index], interval);
 262     // Reschedule ourself
 263     ts1.scheduleTimeout(&scheduler, milliseconds(1));
 264     ++index;
 265   };
 266
 267   // Go ahead and schedule the first timeout now.
 268   //scheduler.fn();
 269
 270   TimePoint start;
 271   eventBase.loop();
 272   TimePoint end;
 273
 274   // We scheduled timeouts 1ms apart, when the HHWheelTimer is only allowed
 275   // to wake up at most once every 3ms.  It will therefore wake up every 3ms
 276   // and fire groups of approximately 3 timeouts at a time.
 277   //
 278   // This is "approximately 3" since it may get slightly behind and fire 4 in
 279   // one interval, etc.  T_CHECK_TIMEOUT normally allows a few milliseconds of
 280   // tolerance.  We have to add the same into our checking algorithm here.
 281   for (uint32_t idx = 0; idx < numTimeouts; ++idx) {
 282     ASSERT_EQ(timeouts[idx].timestamps.size(), 2);
 283
 284     TimePoint scheduledTime(timeouts[idx].timestamps[0]);
 285     TimePoint firedTime(timeouts[idx].timestamps[1]);
 286
 287     // Assert that the timeout fired at roughly the right time.
 288     // T_CHECK_TIMEOUT() normally has a tolerance of 5ms.  Allow an additional
 289     // atMostEveryN.
 290     milliseconds tolerance = milliseconds(5) + interval;
 291     T_CHECK_TIMEOUT(scheduledTime, firedTime, atMostEveryN, tolerance);
 292
 293     // Assert that the difference between the previous timeout and now was
 294     // either very small (fired in the same event loop), or larger than
 295     // atMostEveryN.
 296     if (idx == 0) {
 297       // no previous value
 298       continue;
 299     }
 300     TimePoint prev(timeouts[idx - 1].timestamps[1]);
 301
 302     auto delta = (firedTime.getTimeStart() - prev.getTimeEnd()) -
 303       (firedTime.getTimeWaiting() - prev.getTimeWaiting());
 304     if (delta > milliseconds(1)) {
 305       T_CHECK_TIMEOUT(prev, firedTime, atMostEveryN);
 306     }
 307   }
 308 }
 309
 310 /*
 311  * Test an event loop that is blocking
 312  */
 313
 314 TEST(HHWheelTimerTest, SlowLoop) {
 315   EventBase eventBase;
 316   StackWheelTimer t(&eventBase, milliseconds(1));
 317
 318   TestTimeout t1;
 319   TestTimeout t2;
 320
 321   ASSERT_EQ(t.count(), 0);
 322
 323   eventBase.runInLoop([](){usleep(10000);});
 324   t.scheduleTimeout(&t1, milliseconds(5));
 325
 326   ASSERT_EQ(t.count(), 1);
 327
 328   TimePoint start;
 329   eventBase.loop();
 330   TimePoint end;
 331
 332   ASSERT_EQ(t1.timestamps.size(), 1);
 333   ASSERT_EQ(t.count(), 0);
 334
 335   // Check that the timeout was delayed by sleep
 336   T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(15), milliseconds(1));
 337   T_CHECK_TIMEOUT(start, end, milliseconds(15), milliseconds(1));
 338
 339   // Try it again, this time with catchup timing every loop
 340   t.setCatchupEveryN(1);
 341
 342   eventBase.runInLoop([](){usleep(10000);});
 343   t.scheduleTimeout(&t2, milliseconds(5));
 344
 345   ASSERT_EQ(t.count(), 1);
 346
 347   TimePoint start2;
 348   eventBase.loop();
 349   TimePoint end2;
 350
 351   ASSERT_EQ(t2.timestamps.size(), 1);
 352   ASSERT_EQ(t.count(), 0);
 353
 354   // Check that the timeout was NOT delayed by sleep
 355   T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(10), milliseconds(1));
 356   T_CHECK_TIMEOUT(start2, end2, milliseconds(10), milliseconds(1));
 357 }