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