faux-folly/folly/futures/test/TimerMapTest.cpp

/*
 * Copyright 2015 Nest Labs, Inc. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <gtest/gtest.h>

#include <folly/futures/detail/TimerMap.h>

#include <thread>
#include <atomic>

//#define ADD_DEBUGGING_OUTPUT

/* The DEBUG(x) macro will include the expression in the compilation
 * unit if ADD_DEBUGGING_OUTPUT is defined. Otherwise, the expression
 * is removed by the preprocessor. It is expected that DEBUG(x) has
 * a semicolon following it: DEBUG(x);
 */
#ifdef ADD_DEBUGGING_OUTPUT
#define DEBUG(x) x
#else
#define DEBUG(x) ((void)0)
#endif

using namespace folly;
using folly::detail::TimerMap;
using std::cout;
using std::endl;
using std::atomic;

TEST(TimerMap, PleaseCompile)
{
    TimerMap tm(std::chrono::milliseconds(20));
}

TEST(TimerMap, GetTick)
{
    {
        auto tick = std::chrono::milliseconds(20);
        TimerMap tm(tick);
        EXPECT_EQ(tick, tm.getTick());
    }

    {
        auto tick = std::chrono::milliseconds(67);
        TimerMap tm(tick);
        EXPECT_EQ(tick, tm.getTick());
    }
}

TEST(TimerMap, OneTimer)
{
    TimerMap tm(std::chrono::milliseconds(20));
    const std::chrono::milliseconds delay(1000);
    bool to = false;

    EXPECT_TRUE(tm.empty());
    tm.scheduleTimeout(delay, [&]() {
            to = true;
        });
    EXPECT_FALSE(tm.empty());

    EXPECT_FALSE(to);
    auto epoch = TimerMap::clock_type::now();

    do {
        auto n = TimerMap::clock_type::now();
        auto later = tm.nextTimeout();
        auto elapsed = n - epoch;
        auto wait = later - n;

        if (!tm.empty()) {
            EXPECT_LE(elapsed, delay);
            EXPECT_LE(wait, tm.getTick());
        } else {
            EXPECT_GE(elapsed, delay);
            EXPECT_LE(wait, tm.getTick());
        }

        std::this_thread::sleep_for(wait);
        EXPECT_FALSE(to);
        tm.invokeTimers();
    } while (!tm.empty());


    EXPECT_TRUE(to);
    EXPECT_TRUE(tm.empty());
}

/* Test that >1 timers with the same execution time will all get fired. */
TEST(TimerMap, IdenticalTimers)
{
    TimerMap tm(std::chrono::milliseconds(20));
    auto now = TimerMap::clock_type::now();
    auto expire = now + std::chrono::milliseconds(20);
    bool one = false;
    bool two = false;
    bool three = false;

    EXPECT_TRUE(tm.empty());
    tm.scheduleAlarm(expire, [&]() { one = true; });
    EXPECT_FALSE(tm.empty());
    tm.scheduleAlarm(expire, [&]() { two = true; });
    EXPECT_FALSE(tm.empty());
    tm.scheduleAlarm(expire, [&]() { three = true; });
    EXPECT_FALSE(tm.empty());

    std::this_thread::sleep_for(std::chrono::milliseconds(20));

    EXPECT_FALSE(one);
    EXPECT_FALSE(two);
    EXPECT_FALSE(three);
    EXPECT_FALSE(tm.empty());
    while (!tm.empty()) {
        tm.invokeTimers();
    }
    EXPECT_TRUE(tm.empty());
    EXPECT_TRUE(one);
    EXPECT_TRUE(two);
    EXPECT_TRUE(three);
}

/* Test that timers come out in proper order */
TEST(TimerMap, timerSequencing)
{
    const std::chrono::milliseconds ten_ms(10);
    const std::chrono::milliseconds twenty_ms(20);
    const std::chrono::milliseconds now(0);
    TimerMap tm(std::chrono::milliseconds(1));
    atomic<unsigned> ctr(0);

    tm.scheduleTimeout(twenty_ms, [&] {
            unsigned exp = 2;
            EXPECT_TRUE(ctr.compare_exchange_strong(exp, 3));
            EXPECT_EQ(2, exp);
        });
    tm.scheduleTimeout(ten_ms, [&] {
            unsigned exp = 1;
            EXPECT_TRUE(ctr.compare_exchange_strong(exp, 2));
            EXPECT_EQ(1, exp);
        });
    tm.scheduleTimeout(now, [&] {
            unsigned exp = 0;
            EXPECT_TRUE(ctr.compare_exchange_strong(exp, 1));
            EXPECT_EQ(0, exp);
        });

    while (!tm.empty()) {
        tm.invokeTimers();
    }

    EXPECT_EQ(3, ctr);
}

#ifndef ARRAY_SIZE
#define ARRAY_SIZE(ra) (sizeof(ra)/sizeof(ra[0]))
#endif

namespace {

std::ostream& operator<<(std::ostream& os, const std::chrono::steady_clock::time_point& tp)
{
    os << tp.time_since_epoch().count();
    return os;
}

} /* anonymous namespace */

TEST(TimerMap, SeveralTimers)
{
    /* Set high resolution so tests aren't brittle to timings */
    TimerMap tm(std::chrono::milliseconds(250));
    struct timeout_data {
        std::chrono::milliseconds delay;
        bool value;
    };
    using msecs = std::chrono::milliseconds;

    timeout_data timeouts[] = {
        { msecs(100), false }, // 0: 2nd pass
        { msecs( 50), false }, // 1: 2nd pass
        { msecs(700), false }, // 2: 4th pass
        { msecs(666), false }, // 3: 4th pass
        { msecs(  0), false }, // 4: 1st pass (immediate)
        { msecs(300), false }, // 5: 3rd pass
        { msecs( 10), false }, // 6: 2nd pass
        { msecs(400), false }, // 7: 3rd pass
        { msecs(900), false }, // 8: 5th pass
        { msecs(410), false }, // 9: 3rd pass
    };

    for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
        tm.scheduleTimeout(timeouts[k].delay, [k, &timeouts]() {
                timeouts[k].value = true;
            });
    }

    std::set<unsigned> complete;

    // 1st pass: 4
    {
        auto next = tm.nextTimeout();
        std::this_thread::sleep_until(next);
        auto n = TimerMap::clock_type::now();
        EXPECT_LT(next, n);
        tm.invokeTimers();

        complete.insert(4);
        DEBUG(cout  << "1ST PASS...\n");
        for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
            DEBUG(cout << k << "\n");
            if (complete.find(k) == complete.end()) {
                EXPECT_FALSE(timeouts[k].value);
            } else {
                EXPECT_TRUE(timeouts[k].value);
            }
        }
        DEBUG(cout << endl);
    }

    // 2nd pass: 0, 1, 6
    {
        auto next = tm.nextTimeout();
        std::this_thread::sleep_until(next);
        auto n = TimerMap::clock_type::now();
        DEBUG(cout << "next = " << next << endl);
        DEBUG(cout << "now  = " << n << endl);
        EXPECT_LT(next, n);
        tm.invokeTimers();

        complete.insert(0);
        complete.insert(1);
        complete.insert(6);
        DEBUG(cout << "2ND PASS...\n");
        for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
            DEBUG(cout << k << "\n");
            if (complete.find(k) == complete.end()) {
                EXPECT_FALSE(timeouts[k].value);
            } else {
                EXPECT_TRUE(timeouts[k].value);
            }
        }
        DEBUG(cout << endl);
    }

    // 3rd pass: 5, 7, 9
    {
        auto next = tm.nextTimeout();
        std::this_thread::sleep_until(next);
        auto n = TimerMap::clock_type::now();
        DEBUG(cout << "next = " << next << endl);
        DEBUG(cout << "now  = " << n << endl);
        EXPECT_LT(next, n);
        tm.invokeTimers();

        complete.insert(5);
        complete.insert(7);
        complete.insert(9);
        DEBUG(cout << "3RD PASS...\n");
        for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
            DEBUG(cout << k << "\n");
            if (complete.find(k) == complete.end()) {
                EXPECT_FALSE(timeouts[k].value);
            } else {
                EXPECT_TRUE(timeouts[k].value);
            }
        }
        DEBUG(cout << endl);
    }

    // 4th pass: 2, 3
    {
        auto next = tm.nextTimeout();
        std::this_thread::sleep_until(next);
        auto n = TimerMap::clock_type::now();
        DEBUG(cout << "next = " << next << endl);
        DEBUG(cout << "now  = " << n << endl);
        EXPECT_LT(next, n);
        tm.invokeTimers();

        complete.insert(2);
        complete.insert(3);
        DEBUG(cout << "4TH PASS...\n");
        for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
            DEBUG(cout << k << "\n");
            if (complete.find(k) == complete.end()) {
                EXPECT_FALSE(timeouts[k].value);
            } else {
                EXPECT_TRUE(timeouts[k].value);
            }
        }
        DEBUG(cout << endl);
    }

    // 5th pass: 8
    {
        auto next = tm.nextTimeout();
        std::this_thread::sleep_until(next);
        auto n = TimerMap::clock_type::now();
        DEBUG(cout << "next = " << next << endl);
        DEBUG(cout << "now  = " << n << endl);
        EXPECT_LT(next, n);
        tm.invokeTimers();

        complete.insert(8);
        DEBUG(cout << "5TH PASS...\n");
        for (unsigned k = 0 ; k < ARRAY_SIZE(timeouts) ; ++k) {
            DEBUG(cout << k << "\n");
            if (complete.find(k) == complete.end()) {
                EXPECT_FALSE(timeouts[k].value);
            } else {
                EXPECT_TRUE(timeouts[k].value);
            }
        }
        DEBUG(cout << endl);
    }

    EXPECT_TRUE(tm.empty());
}