1// Copyright 2018 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// TODO(joshuseaton): Once std lands in Zircon, simplify everything below.
6
7#include <lib/async-testutils/test_loop.h>
8
9#include <stdlib.h>
10
11#include <fbl/algorithm.h>
12#include <lib/async-testutils/time-keeper.h>
13#include <lib/async/default.h>
14#include <lib/zircon-internal/xorshiftrand.h>
15#include <zircon/syscalls.h>
16
17namespace async {
18namespace {
19
20// Determinisitically updates |m| to point to a pseudo-random number.
21void Randomize(uint32_t* m) {
22  rand32_t r = { .n = *m };
23  *m = rand32(&r);
24}
25
26// Generates a random seed if the environment variable TEST_LOOP_RANDOM_SEED
27// is unset; else returns the value of the latter.
28uint32_t GetRandomSeed() {;
29    uint32_t random_seed;
30    const char* preset = getenv("TEST_LOOP_RANDOM_SEED");
31
32    if (preset) {
33        size_t preset_length = strlen(preset);
34        char* endptr = nullptr;
35        long unsigned preset_seed = strtoul(preset, &endptr, 10);
36        ZX_ASSERT_MSG(preset_seed > 0 && endptr == preset + preset_length,
37                      "ERROR: \"%s\" does not give a valid random seed\n", preset);
38
39        random_seed = static_cast<uint32_t>(preset_seed);
40    } else {
41        zx_cprng_draw(&random_seed, sizeof(uint32_t));
42    }
43
44    printf("\nTEST_LOOP_RANDOM_SEED=\"%u\"\n", random_seed);
45    return random_seed;
46}
47
48} // namespace
49
50class TestLoop::TestLoopTimeKeeper : public TimeKeeper {
51public:
52    TestLoopTimeKeeper() = default;
53    ~TestLoopTimeKeeper() = default;
54
55    zx::time Now() const override { return current_time_; }
56
57    void RegisterTimer(zx::time deadline, TimerDispatcher* dispatcher) override {
58        if (deadline <= current_time_) {
59            dispatcher->FireTimer();
60            return;
61        }
62
63        for (auto& entry : table_) {
64            if (entry.dispatcher == dispatcher) {
65                entry.deadlines.push_back(deadline);
66                return;
67            }
68        }
69
70        DeadlinesByDispatcher entry{};
71        entry.dispatcher = dispatcher;
72        entry.deadlines.push_back(deadline);
73        table_.push_back(fbl::move(entry));
74    }
75
76    void CancelTimers(TimerDispatcher* dispatcher) override {
77        size_t ind = 0;
78        for (; ind < table_.size(); ++ind){
79            if (table_[ind].dispatcher == dispatcher){
80                table_.erase(ind);
81                return;
82            }
83        }
84    }
85
86    void AdvanceTimeTo(zx::time time) {
87        if (time < current_time_) { return; }
88        current_time_ = time;
89
90        for (auto& entry : table_) {
91            if (entry.deadlines.size() == 0) {
92                continue;
93            }
94            zx::time min_deadline =
95              *fbl::min_element(entry.deadlines.begin(), entry.deadlines.end());
96            if (min_deadline > time){
97                continue;
98            }
99            entry.dispatcher->FireTimer();
100
101            size_t end = entry.deadlines.size() - 1;
102            for (size_t i = 0; i <= entry.deadlines.size(); ++i){
103                zx::time back = entry.deadlines[end];
104                entry.deadlines.pop_back();
105                if (back > time) {
106                    entry.deadlines.insert(0, back);
107                    continue;
108                }
109                --end;
110            }
111        }
112    }
113
114private:
115    struct DeadlinesByDispatcher {
116      TimerDispatcher* dispatcher;
117      fbl::Vector<zx::time> deadlines;
118    };
119
120    zx::time current_time_;
121    fbl::Vector<DeadlinesByDispatcher> table_;
122};
123
124
125class TestLoop::TestLoopInterface : public LoopInterface {
126public:
127      TestLoopInterface(TestLoop* loop, TestLoopDispatcher* dispatcher)
128          : loop_(loop), dispatcher_(dispatcher) {}
129
130      ~TestLoopInterface() override {
131          auto& dispatchers = loop_->dispatchers_;
132          for (size_t index = 0; index < dispatchers.size(); ++index) {
133              if (dispatchers[index].get() == dispatcher_) {
134                  dispatchers.erase(index);
135                  break;
136              }
137          }
138          dispatcher_ = nullptr;
139      }
140
141      async_dispatcher_t* dispatcher() override { return dispatcher_; }
142
143private:
144    TestLoop* const loop_;
145    TestLoopDispatcher* dispatcher_;
146};
147
148TestLoop::TestLoop()
149    : time_keeper_(new TestLoopTimeKeeper()), initial_state_(GetRandomSeed()), state_(initial_state_) {
150    dispatchers_.push_back(fbl::make_unique<TestLoopDispatcher>(time_keeper_.get()));
151    async_set_default_dispatcher(dispatchers_[0].get());
152}
153
154TestLoop::~TestLoop() {
155    async_set_default_dispatcher(nullptr);
156}
157
158async_dispatcher_t* TestLoop::dispatcher() {
159    return dispatchers_[0].get();
160}
161
162fbl::unique_ptr<LoopInterface> TestLoop::StartNewLoop() {
163    dispatchers_.push_back(fbl::make_unique<TestLoopDispatcher>(time_keeper_.get()));
164    auto* new_dispatcher = dispatchers_[dispatchers_.size() - 1].get();
165    return fbl::make_unique<TestLoopInterface>(this, new_dispatcher);
166}
167
168zx::time TestLoop::Now() const {
169    return time_keeper_->Now();
170}
171
172void TestLoop::Quit() {
173    has_quit_ = true;
174}
175
176
177void TestLoop::AdvanceTimeByEpsilon() {
178    time_keeper_->AdvanceTimeTo(Now() + zx::duration(1));
179}
180
181bool TestLoop::RunUntil(zx::time deadline) {
182    ZX_ASSERT(!is_running_);
183    is_running_ = true;
184    bool did_work = false;
185    while (!has_quit_) {
186        if (!HasPendingWork()) {
187            zx::time next_due_time = GetNextTaskDueTime();
188            if (next_due_time > deadline) {
189                time_keeper_->AdvanceTimeTo(deadline);
190                break;
191            }
192            time_keeper_->AdvanceTimeTo(next_due_time);
193        }
194
195        Randomize(&state_);
196        size_t current_index = state_ % dispatchers_.size();
197        auto& current_dispatcher = dispatchers_[current_index];
198
199        async_set_default_dispatcher(current_dispatcher.get());
200        did_work |= current_dispatcher->DispatchNextDueMessage();
201        async_set_default_dispatcher(dispatchers_[0].get());
202
203    }
204    is_running_ = false;
205    has_quit_ = false;
206    return did_work;
207}
208
209bool TestLoop::RunFor(zx::duration duration) {
210    return RunUntil(Now() + duration);
211}
212
213bool TestLoop::RunUntilIdle() {
214    return RunUntil(Now());
215}
216
217bool TestLoop::HasPendingWork() {
218    for (auto& dispatcher : dispatchers_) {
219        if (dispatcher->HasPendingWork()) { return true; }
220    }
221    return false;
222}
223
224zx::time TestLoop::GetNextTaskDueTime() const {
225  zx::time next_due_time = zx::time::infinite();
226  for (auto& dispatcher : dispatchers_) {
227      next_due_time =
228          fbl::min<zx::time>(next_due_time, dispatcher->GetNextTaskDueTime());
229  }
230  return next_due_time;
231}
232
233} // namespace async
234