1/*
2 * Copyright 2014-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <folly/io/async/HHWheelTimer.h>
18#include <folly/io/async/EventBase.h>
19#include <folly/io/async/test/UndelayedDestruction.h>
20#include <folly/io/async/test/Util.h>
21#include <folly/portability/GTest.h>
22
23using namespace folly;
24using std::chrono::milliseconds;
25
26typedef UndelayedDestruction<HHWheelTimer> StackWheelTimer;
27
28class TestTimeout : public HHWheelTimer::Callback {
29 public:
30 TestTimeout() {}
31 TestTimeout(HHWheelTimer* t, milliseconds timeout) {
32 t->scheduleTimeout(this, timeout);
33 }
34
35 void timeoutExpired() noexcept override {
36 timestamps.emplace_back();
37 if (fn) {
38 fn();
39 }
40 }
41
42 void callbackCanceled() noexcept override {
43 canceledTimestamps.emplace_back();
44 if (fn) {
45 fn();
46 }
47 }
48
49 std::deque<TimePoint> timestamps;
50 std::deque<TimePoint> canceledTimestamps;
51 std::function<void()> fn;
52};
53
54struct HHWheelTimerTest : public ::testing::Test {
55 EventBase eventBase;
56};
57
58/*
59 * Test firing some simple timeouts that are fired once and never rescheduled
60 */
61TEST_F(HHWheelTimerTest, FireOnce) {
62 StackWheelTimer t(&eventBase, milliseconds(1));
63
64 TestTimeout t1;
65 TestTimeout t2;
66 TestTimeout t3;
67
68 ASSERT_EQ(t.count(), 0);
69
70 t.scheduleTimeout(&t1, milliseconds(5));
71 t.scheduleTimeout(&t2, milliseconds(5));
72 // Verify scheduling it twice cancels, then schedules.
73 // Should only get one callback.
74 t.scheduleTimeout(&t2, milliseconds(5));
75 t.scheduleTimeout(&t3, milliseconds(10));
76
77 ASSERT_EQ(t.count(), 3);
78
79 TimePoint start;
80 eventBase.loop();
81 TimePoint end;
82
83 ASSERT_EQ(t1.timestamps.size(), 1);
84 ASSERT_EQ(t2.timestamps.size(), 1);
85 ASSERT_EQ(t3.timestamps.size(), 1);
86
87 ASSERT_EQ(t.count(), 0);
88
89 T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
90 T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
91 T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
92 T_CHECK_TIMEOUT(start, end, milliseconds(10));
93}
94
95/*
96 * Test scheduling a timeout from another timeout callback.
97 */
98TEST_F(HHWheelTimerTest, TestSchedulingWithinCallback) {
99 HHWheelTimer& t = eventBase.timer();
100
101 TestTimeout t1, t2;
102
103 t.scheduleTimeout(&t1, milliseconds(500));
104 t1.fn = [&] {
105 t.scheduleTimeout(&t2, milliseconds(1));
106 std::this_thread::sleep_for(std::chrono::milliseconds(5));
107 };
108 // If t is in an inconsistent state, detachEventBase should fail.
109 t2.fn = [&] { t.detachEventBase(); };
110
111 ASSERT_EQ(t.count(), 1);
112
113 eventBase.loop();
114
115 ASSERT_EQ(t.count(), 0);
116 ASSERT_EQ(t1.timestamps.size(), 1);
117 ASSERT_EQ(t2.timestamps.size(), 1);
118}
119
120/*
121 * Test changing default-timeout in timer.
122 */
123TEST_F(HHWheelTimerTest, TestSetDefaultTimeout) {
124 HHWheelTimer& t = eventBase.timer();
125
126 t.setDefaultTimeout(milliseconds(1000));
127 // verify: default-time has been modified
128 ASSERT_EQ(t.getDefaultTimeout(), milliseconds(1000));
129}
130
131/*
132 * Test cancelling a timeout when it is scheduled to be fired right away.
133 */
134
135TEST_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
216TEST_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
238 TimePoint start;
239 eventBase.loop();
240 TimePoint end;
241
242 ASSERT_EQ(t5_1.timestamps.size(), 1);
243 T_CHECK_TIMEOUT(start, t5_1.timestamps[0], milliseconds(5));
244 ASSERT_EQ(t5_2.timestamps.size(), 1);
245 T_CHECK_TIMEOUT(start, t5_2.timestamps[0], milliseconds(5));
246
247 ASSERT_EQ(t5_3.timestamps.size(), 0);
248 ASSERT_EQ(t10_1.timestamps.size(), 0);
249 ASSERT_EQ(t10_2.timestamps.size(), 0);
250
251 T_CHECK_TIMEOUT(start, end, milliseconds(5));
252}
253
254/*
255 * Test an event scheduled before the last event fires on time
256 */
257
258TEST_F(HHWheelTimerTest, SlowFast) {
259 StackWheelTimer t(&eventBase, milliseconds(1));
260
261 TestTimeout t1;
262 TestTimeout t2;
263
264 ASSERT_EQ(t.count(), 0);
265
266 t.scheduleTimeout(&t1, milliseconds(10));
267 t.scheduleTimeout(&t2, milliseconds(5));
268
269 ASSERT_EQ(t.count(), 2);
270
271 TimePoint start;
272 eventBase.loop();
273 TimePoint end;
274
275 ASSERT_EQ(t1.timestamps.size(), 1);
276 ASSERT_EQ(t2.timestamps.size(), 1);
277 ASSERT_EQ(t.count(), 0);
278
279 // Check that the timeout was delayed by sleep
280 T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(10), milliseconds(1));
281 T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5), milliseconds(1));
282}
283
284TEST_F(HHWheelTimerTest, ReschedTest) {
285 StackWheelTimer t(&eventBase, milliseconds(1));
286
287 TestTimeout t1;
288 TestTimeout t2;
289
290 ASSERT_EQ(t.count(), 0);
291
292 t.scheduleTimeout(&t1, milliseconds(128));
293 TimePoint start2;
294 t1.fn = [&]() {
295 t.scheduleTimeout(&t2, milliseconds(255)); // WHEEL_SIZE - 1
296 start2.reset();
297 ASSERT_EQ(t.count(), 1);
298 };
299
300 ASSERT_EQ(t.count(), 1);
301
302 TimePoint start;
303 eventBase.loop();
304 TimePoint end;
305
306 ASSERT_EQ(t1.timestamps.size(), 1);
307 ASSERT_EQ(t2.timestamps.size(), 1);
308 ASSERT_EQ(t.count(), 0);
309
310 T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
311 T_CHECK_TIMEOUT(start2, t2.timestamps[0], milliseconds(255), milliseconds(1));
312}
313
314TEST_F(HHWheelTimerTest, DeleteWheelInTimeout) {
315 auto t = HHWheelTimer::newTimer(&eventBase, milliseconds(1));
316
317 TestTimeout t1;
318 TestTimeout t2;
319 TestTimeout t3;
320
321 ASSERT_EQ(t->count(), 0);
322
323 t->scheduleTimeout(&t1, milliseconds(128));
324 t->scheduleTimeout(&t2, milliseconds(128));
325 t->scheduleTimeout(&t3, milliseconds(128));
326 t1.fn = [&]() { t2.cancelTimeout(); };
327 t3.fn = [&]() { t.reset(); };
328
329 ASSERT_EQ(t->count(), 3);
330
331 TimePoint start;
332 eventBase.loop();
333 TimePoint end;
334
335 ASSERT_EQ(t1.timestamps.size(), 1);
336 ASSERT_EQ(t2.timestamps.size(), 0);
337
338 T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(128), milliseconds(1));
339}
340
341/*
342 * Test scheduling a mix of timers with default timeout and variable timeout.
343 */
344TEST_F(HHWheelTimerTest, DefaultTimeout) {
345 milliseconds defaultTimeout(milliseconds(5));
346 StackWheelTimer t(
347 &eventBase,
348 milliseconds(1),
349 AsyncTimeout::InternalEnum::NORMAL,
350 defaultTimeout);
351
352 TestTimeout t1;
353 TestTimeout t2;
354
355 ASSERT_EQ(t.count(), 0);
356 ASSERT_EQ(t.getDefaultTimeout(), defaultTimeout);
357
358 t.scheduleTimeout(&t1);
359 t.scheduleTimeout(&t2, milliseconds(10));
360
361 ASSERT_EQ(t.count(), 2);
362
363 TimePoint start;
364 eventBase.loop();
365 TimePoint end;
366
367 ASSERT_EQ(t1.timestamps.size(), 1);
368 ASSERT_EQ(t2.timestamps.size(), 1);
369
370 ASSERT_EQ(t.count(), 0);
371
372 T_CHECK_TIMEOUT(start, t1.timestamps[0], defaultTimeout);
373 T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(10));
374 T_CHECK_TIMEOUT(start, end, milliseconds(10));
375}
376
377TEST_F(HHWheelTimerTest, lambda) {
378 StackWheelTimer t(&eventBase, milliseconds(1));
379 size_t count = 0;
380 t.scheduleTimeoutFn([&] { count++; }, milliseconds(1));
381 eventBase.loop();
382 EXPECT_EQ(1, count);
383}
384
385// shouldn't crash because we swallow and log the error (you'll have to look
386// at the console to confirm logging)
387TEST_F(HHWheelTimerTest, lambdaThrows) {
388 StackWheelTimer t(&eventBase, milliseconds(1));
389 t.scheduleTimeoutFn(
390 [&] { throw std::runtime_error("expected"); }, milliseconds(1));
391 eventBase.loop();
392}
393
394TEST_F(HHWheelTimerTest, cancelAll) {
395 StackWheelTimer t(&eventBase, milliseconds(1));
396 TestTimeout t1;
397 TestTimeout t2;
398 t.scheduleTimeout(&t1, std::chrono::milliseconds(1));
399 t.scheduleTimeout(&t2, std::chrono::milliseconds(1));
400 size_t canceled = 0;
401 t1.fn = [&] { canceled += t.cancelAll(); };
402 t2.fn = [&] { canceled += t.cancelAll(); };
403 // Sleep 20ms to ensure both timeouts will fire in a single event (in case
404 // they ended up in different slots)
405 ::usleep(20000);
406 eventBase.loop();
407 EXPECT_EQ(1, t1.canceledTimestamps.size() + t2.canceledTimestamps.size());
408 EXPECT_EQ(1, canceled);
409}
410
411TEST_F(HHWheelTimerTest, IntrusivePtr) {
412 HHWheelTimer::UniquePtr t(
413 HHWheelTimer::newTimer(&eventBase, milliseconds(1)));
414
415 TestTimeout t1;
416 TestTimeout t2;
417 TestTimeout t3;
418
419 ASSERT_EQ(t->count(), 0);
420
421 t->scheduleTimeout(&t1, milliseconds(5));
422 t->scheduleTimeout(&t2, milliseconds(5));
423
424 DelayedDestruction::IntrusivePtr<HHWheelTimer> s(t);
425
426 s->scheduleTimeout(&t3, milliseconds(10));
427
428 ASSERT_EQ(t->count(), 3);
429
430 // Kill the UniquePtr, but the SharedPtr keeps it alive
431 t.reset();
432
433 TimePoint start;
434 eventBase.loop();
435 TimePoint end;
436
437 ASSERT_EQ(t1.timestamps.size(), 1);
438 ASSERT_EQ(t2.timestamps.size(), 1);
439 ASSERT_EQ(t3.timestamps.size(), 1);
440
441 ASSERT_EQ(s->count(), 0);
442
443 T_CHECK_TIMEOUT(start, t1.timestamps[0], milliseconds(5));
444 T_CHECK_TIMEOUT(start, t2.timestamps[0], milliseconds(5));
445 T_CHECK_TIMEOUT(start, t3.timestamps[0], milliseconds(10));
446 T_CHECK_TIMEOUT(start, end, milliseconds(10));
447}
448
449TEST_F(HHWheelTimerTest, GetTimeRemaining) {
450 StackWheelTimer t(&eventBase, milliseconds(1));
451 TestTimeout t1;
452
453 // Not scheduled yet, time remaining should be zero
454 ASSERT_EQ(t1.getTimeRemaining(), milliseconds(0));
455 ASSERT_EQ(t.count(), 0);
456
457 // Scheduled, time remaining should be less than or equal to the scheduled
458 // timeout
459 t.scheduleTimeout(&t1, milliseconds(10));
460 ASSERT_LE(t1.getTimeRemaining(), milliseconds(10));
461
462 TimePoint start;
463 eventBase.loop();
464 TimePoint end;
465
466 // Expired and time remaining should be zero
467 ASSERT_EQ(t1.getTimeRemaining(), milliseconds(0));
468
469 ASSERT_EQ(t.count(), 0);
470 T_CHECK_TIMEOUT(start, end, milliseconds(10));
471}
472
473TEST_F(HHWheelTimerTest, prematureTimeout) {
474 StackWheelTimer t(&eventBase, milliseconds(10));
475 TestTimeout t1;
476 TestTimeout t2;
477 // Schedule the timeout for the nextTick of timer
478 t.scheduleTimeout(&t1, std::chrono::milliseconds(1));
479 // Make sure that time is past that tick.
480 ::usleep(10000);
481 // Schedule the timeout for the +255 tick, due to sleep above it will overlap
482 // with what would be ran on the next timeoutExpired of the timer.
483 auto timeout = std::chrono::milliseconds(2555);
484 t.scheduleTimeout(&t2, std::chrono::milliseconds(2555));
485 auto start = std::chrono::steady_clock::now();
486 eventBase.loop();
487 ASSERT_EQ(t2.timestamps.size(), 1);
488 auto elapsedMs = std::chrono::duration_cast<std::chrono::milliseconds>(
489 t2.timestamps[0].getTime() - start);
490 EXPECT_GE(elapsedMs.count(), timeout.count());
491}
492