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 #include <lib/fit/scheduler.h>
6 #include <unittest/unittest.h>
7
8 #include "unittest_utils.h"
9
10 namespace {
11
12 class fake_context : public fit::context {
13 public:
executor() const14 fit::executor* executor() const override {
15 ASSERT_CRITICAL(false);
16 }
suspend_task()17 fit::suspended_task suspend_task() override {
18 ASSERT_CRITICAL(false);
19 }
20 };
21
make_pending_task(uint64_t * counter)22 fit::pending_task make_pending_task(uint64_t* counter) {
23 return fit::make_promise([counter] { (*counter)++; });
24 }
25
initial_state()26 bool initial_state() {
27 BEGIN_TEST;
28
29 fit::subtle::scheduler scheduler;
30 EXPECT_FALSE(scheduler.has_runnable_tasks());
31 EXPECT_FALSE(scheduler.has_suspended_tasks());
32 EXPECT_FALSE(scheduler.has_outstanding_tickets());
33
34 END_TEST;
35 }
36
schedule_task()37 bool schedule_task() {
38 BEGIN_TEST;
39
40 fit::subtle::scheduler scheduler;
41 fit::subtle::scheduler::task_queue tasks;
42 fake_context context;
43 uint64_t run_count[3] = {};
44
45 // Initially there are no tasks.
46 scheduler.take_runnable_tasks(&tasks);
47 EXPECT_TRUE(tasks.empty());
48
49 // Schedule and run one task.
50 scheduler.schedule_task(make_pending_task(&run_count[0]));
51 EXPECT_TRUE(scheduler.has_runnable_tasks());
52 EXPECT_FALSE(scheduler.has_suspended_tasks());
53 EXPECT_FALSE(scheduler.has_outstanding_tickets());
54 scheduler.take_runnable_tasks(&tasks);
55 EXPECT_EQ(1, tasks.size());
56 tasks.front()(context);
57 EXPECT_EQ(1, run_count[0]);
58 tasks.pop();
59
60 // Run a couple more, ensure that they come out in queue order.
61 scheduler.schedule_task(make_pending_task(&run_count[0]));
62 scheduler.schedule_task(make_pending_task(&run_count[1]));
63 scheduler.schedule_task(make_pending_task(&run_count[2]));
64 EXPECT_TRUE(scheduler.has_runnable_tasks());
65 EXPECT_FALSE(scheduler.has_suspended_tasks());
66 EXPECT_FALSE(scheduler.has_outstanding_tickets());
67 scheduler.take_runnable_tasks(&tasks);
68 EXPECT_EQ(3, tasks.size());
69 tasks.front()(context);
70 EXPECT_EQ(2, run_count[0]);
71 EXPECT_EQ(0, run_count[1]);
72 EXPECT_EQ(0, run_count[2]);
73 tasks.pop();
74 tasks.front()(context);
75 EXPECT_EQ(2, run_count[0]);
76 EXPECT_EQ(1, run_count[1]);
77 EXPECT_EQ(0, run_count[2]);
78 tasks.pop();
79 tasks.front()(context);
80 EXPECT_EQ(2, run_count[0]);
81 EXPECT_EQ(1, run_count[1]);
82 EXPECT_EQ(1, run_count[2]);
83 tasks.pop();
84
85 // Once we're done, no tasks are left.
86 scheduler.take_runnable_tasks(&tasks);
87 EXPECT_TRUE(tasks.empty());
88
89 END_TEST;
90 }
91
ticket_obtain_finalize_without_task()92 bool ticket_obtain_finalize_without_task() {
93 BEGIN_TEST;
94
95 fit::subtle::scheduler scheduler;
96
97 fit::suspended_task::ticket t = scheduler.obtain_ticket();
98 EXPECT_FALSE(scheduler.has_runnable_tasks());
99 EXPECT_FALSE(scheduler.has_suspended_tasks());
100 EXPECT_TRUE(scheduler.has_outstanding_tickets());
101
102 fit::pending_task task;
103 scheduler.finalize_ticket(t, &task);
104 EXPECT_FALSE(scheduler.has_runnable_tasks());
105 EXPECT_FALSE(scheduler.has_suspended_tasks());
106 EXPECT_FALSE(scheduler.has_outstanding_tickets());
107
108 END_TEST;
109 }
110
ticket_obtain_finalize_with_task()111 bool ticket_obtain_finalize_with_task() {
112 BEGIN_TEST;
113
114 fit::subtle::scheduler scheduler;
115
116 fit::suspended_task::ticket t = scheduler.obtain_ticket();
117 EXPECT_FALSE(scheduler.has_runnable_tasks());
118 EXPECT_FALSE(scheduler.has_suspended_tasks());
119 EXPECT_TRUE(scheduler.has_outstanding_tickets());
120
121 uint64_t run_count = 0;
122 fit::pending_task p = make_pending_task(&run_count);
123 scheduler.finalize_ticket(t, &p);
124 EXPECT_FALSE(scheduler.has_runnable_tasks());
125 EXPECT_FALSE(scheduler.has_suspended_tasks());
126 EXPECT_FALSE(scheduler.has_outstanding_tickets());
127 EXPECT_TRUE(p); // didn't take ownership
128
129 END_TEST;
130 }
131
ticket_obtain2_duplicate_finalize_release()132 bool ticket_obtain2_duplicate_finalize_release() {
133 BEGIN_TEST;
134
135 fit::subtle::scheduler scheduler;
136
137 fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
138 scheduler.duplicate_ticket(t);
139 EXPECT_FALSE(scheduler.has_runnable_tasks());
140 EXPECT_FALSE(scheduler.has_suspended_tasks());
141 EXPECT_TRUE(scheduler.has_outstanding_tickets());
142
143 uint64_t run_count = 0;
144 fit::pending_task p = make_pending_task(&run_count);
145 scheduler.finalize_ticket(t, &p);
146 EXPECT_FALSE(scheduler.has_runnable_tasks());
147 EXPECT_TRUE(scheduler.has_suspended_tasks());
148 EXPECT_TRUE(scheduler.has_outstanding_tickets());
149 EXPECT_FALSE(p); // took ownership
150
151 p = scheduler.release_ticket(t);
152 EXPECT_FALSE(scheduler.has_runnable_tasks());
153 EXPECT_TRUE(scheduler.has_suspended_tasks());
154 EXPECT_TRUE(scheduler.has_outstanding_tickets());
155 EXPECT_FALSE(p); // ticket still has one ref
156
157 p = scheduler.release_ticket(t);
158 EXPECT_FALSE(scheduler.has_runnable_tasks());
159 EXPECT_FALSE(scheduler.has_suspended_tasks());
160 EXPECT_FALSE(scheduler.has_outstanding_tickets());
161 EXPECT_TRUE(p); // ticket fully unref'd so task ownership returned
162
163 END_TEST;
164 }
165
ticket_obtain2_duplicate_finalize_resume()166 bool ticket_obtain2_duplicate_finalize_resume() {
167 BEGIN_TEST;
168
169 fit::subtle::scheduler scheduler;
170
171 fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
172 scheduler.duplicate_ticket(t);
173 EXPECT_FALSE(scheduler.has_runnable_tasks());
174 EXPECT_FALSE(scheduler.has_suspended_tasks());
175 EXPECT_TRUE(scheduler.has_outstanding_tickets());
176
177 uint64_t run_count = 0;
178 fit::pending_task p = make_pending_task(&run_count);
179 scheduler.finalize_ticket(t, &p);
180 EXPECT_FALSE(scheduler.has_runnable_tasks());
181 EXPECT_TRUE(scheduler.has_suspended_tasks());
182 EXPECT_TRUE(scheduler.has_outstanding_tickets());
183 EXPECT_FALSE(p); // took ownership
184
185 scheduler.resume_task_with_ticket(t);
186 EXPECT_TRUE(scheduler.has_runnable_tasks());
187 EXPECT_FALSE(scheduler.has_suspended_tasks());
188 EXPECT_TRUE(scheduler.has_outstanding_tickets());
189
190 p = scheduler.release_ticket(t);
191 EXPECT_TRUE(scheduler.has_runnable_tasks());
192 EXPECT_FALSE(scheduler.has_suspended_tasks());
193 EXPECT_FALSE(scheduler.has_outstanding_tickets());
194 EXPECT_FALSE(p); // ticket was already resumed, nothing to return
195
196 fit::subtle::scheduler::task_queue tasks;
197 scheduler.take_runnable_tasks(&tasks);
198 EXPECT_EQ(1, tasks.size());
199
200 fake_context context;
201 tasks.front()(context);
202 EXPECT_EQ(1, run_count);
203
204 END_TEST;
205 }
206
ticket_obtain2_release_finalize()207 bool ticket_obtain2_release_finalize() {
208 BEGIN_TEST;
209
210 fit::subtle::scheduler scheduler;
211
212 fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
213 EXPECT_FALSE(scheduler.has_runnable_tasks());
214 EXPECT_FALSE(scheduler.has_suspended_tasks());
215 EXPECT_TRUE(scheduler.has_outstanding_tickets());
216
217 fit::pending_task p = scheduler.release_ticket(t);
218 EXPECT_FALSE(scheduler.has_runnable_tasks());
219 EXPECT_FALSE(scheduler.has_suspended_tasks());
220 EXPECT_TRUE(scheduler.has_outstanding_tickets());
221 EXPECT_FALSE(p); // ticket still has one ref
222
223 uint64_t run_count = 0;
224 p = make_pending_task(&run_count);
225 scheduler.finalize_ticket(t, &p);
226 EXPECT_FALSE(scheduler.has_runnable_tasks());
227 EXPECT_FALSE(scheduler.has_suspended_tasks());
228 EXPECT_FALSE(scheduler.has_outstanding_tickets());
229 EXPECT_TRUE(p); // ticket ref-count reached zero, so ownership not taken
230
231 END_TEST;
232 }
233
ticket_obtain2_resume_finalize()234 bool ticket_obtain2_resume_finalize() {
235 BEGIN_TEST;
236
237 fit::subtle::scheduler scheduler;
238
239 fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
240 EXPECT_FALSE(scheduler.has_runnable_tasks());
241 EXPECT_FALSE(scheduler.has_suspended_tasks());
242 EXPECT_TRUE(scheduler.has_outstanding_tickets());
243
244 scheduler.resume_task_with_ticket(t);
245 EXPECT_FALSE(scheduler.has_runnable_tasks());
246 EXPECT_FALSE(scheduler.has_suspended_tasks());
247 EXPECT_TRUE(scheduler.has_outstanding_tickets());
248
249 uint64_t run_count = 0;
250 fit::pending_task p = make_pending_task(&run_count);
251 scheduler.finalize_ticket(t, &p);
252 EXPECT_TRUE(scheduler.has_runnable_tasks());
253 EXPECT_FALSE(scheduler.has_suspended_tasks());
254 EXPECT_FALSE(scheduler.has_outstanding_tickets());
255 EXPECT_FALSE(p); // took ownership since task already resumed
256
257 fit::subtle::scheduler::task_queue tasks;
258 scheduler.take_runnable_tasks(&tasks);
259 EXPECT_EQ(1, tasks.size());
260
261 fake_context context;
262 tasks.front()(context);
263 EXPECT_EQ(1, run_count);
264
265 END_TEST;
266 }
267
take_all_tasks()268 bool take_all_tasks() {
269 BEGIN_TEST;
270
271 fit::subtle::scheduler scheduler;
272 fit::subtle::scheduler::task_queue tasks;
273 fake_context context;
274 uint64_t run_count[6] = {};
275
276 // Initially there are no tasks.
277 scheduler.take_all_tasks(&tasks);
278 EXPECT_TRUE(tasks.empty());
279
280 // Schedule a task.
281 scheduler.schedule_task(make_pending_task(&run_count[0]));
282 EXPECT_TRUE(scheduler.has_runnable_tasks());
283
284 // Suspend a task and finalize it without resumption.
285 // This does not leave an outstanding ticket.
286 fit::suspended_task::ticket t1 = scheduler.obtain_ticket();
287 fit::pending_task p1 = make_pending_task(&run_count[1]);
288 scheduler.finalize_ticket(t1, &p1);
289 EXPECT_TRUE(p1); // took ownership
290
291 // Suspend a task and duplicate its ticket.
292 // This leaves an outstanding ticket with an associated task.
293 fit::suspended_task::ticket t2 = scheduler.obtain_ticket();
294 fit::pending_task p2 = make_pending_task(&run_count[2]);
295 scheduler.duplicate_ticket(t2);
296 scheduler.finalize_ticket(t2, &p2);
297 EXPECT_FALSE(p2); // didn't take ownership
298
299 // Suspend a task, duplicate its ticket, then release it.
300 // This does not leave an outstanding ticket.
301 fit::suspended_task::ticket t3 = scheduler.obtain_ticket();
302 fit::pending_task p3 = make_pending_task(&run_count[3]);
303 scheduler.duplicate_ticket(t3);
304 scheduler.finalize_ticket(t3, &p3);
305 EXPECT_FALSE(p3); // didn't take ownership
306 p3 = scheduler.release_ticket(t3);
307 EXPECT_TRUE(p3);
308
309 // Suspend a task, duplicate its ticket, then resume it.
310 // This adds a runnable task but does not leave an outstanding ticket.
311 fit::suspended_task::ticket t4 = scheduler.obtain_ticket();
312 fit::pending_task p4 = make_pending_task(&run_count[4]);
313 scheduler.duplicate_ticket(t4);
314 scheduler.finalize_ticket(t4, &p4);
315 EXPECT_FALSE(p4); // didn't take ownership
316 EXPECT_TRUE(scheduler.resume_task_with_ticket(t4));
317
318 // Suspend a task, duplicate its ticket twice, then resume it.
319 // This adds a runnable task and leaves an outstanding ticket without an
320 // associated task.
321 fit::suspended_task::ticket t5 = scheduler.obtain_ticket();
322 fit::pending_task p5 = make_pending_task(&run_count[5]);
323 scheduler.duplicate_ticket(t5);
324 scheduler.duplicate_ticket(t5);
325 scheduler.finalize_ticket(t5, &p5);
326 EXPECT_FALSE(p5); // didn't take ownership
327 EXPECT_TRUE(scheduler.resume_task_with_ticket(t5));
328
329 // Now take all tasks.
330 // We expect to find tasks that were runnable or associated with
331 // outstanding tickets. Those outstanding tickets will remain, however they
332 // no longer have an associated task (cannot subsequently be resumed).
333 EXPECT_TRUE(scheduler.has_runnable_tasks());
334 EXPECT_TRUE(scheduler.has_suspended_tasks());
335 EXPECT_TRUE(scheduler.has_outstanding_tickets());
336 scheduler.take_all_tasks(&tasks);
337 EXPECT_FALSE(scheduler.has_runnable_tasks());
338 EXPECT_FALSE(scheduler.has_suspended_tasks());
339 EXPECT_TRUE(scheduler.has_outstanding_tickets());
340
341 // Check that we obtained the tasks we expected to obtain, by running them.
342 EXPECT_EQ(4, tasks.size());
343 while (!tasks.empty()) {
344 tasks.front()(context);
345 tasks.pop();
346 }
347 EXPECT_EQ(1, run_count[0]);
348 EXPECT_EQ(0, run_count[1]);
349 EXPECT_EQ(1, run_count[2]);
350 EXPECT_EQ(0, run_count[3]);
351 EXPECT_EQ(1, run_count[4]);
352 EXPECT_EQ(1, run_count[5]);
353
354 // Now that everything is gone, taking all tasks should return an empty set.
355 scheduler.take_all_tasks(&tasks);
356 EXPECT_FALSE(scheduler.has_runnable_tasks());
357 EXPECT_FALSE(scheduler.has_suspended_tasks());
358 EXPECT_TRUE(scheduler.has_outstanding_tickets());
359 EXPECT_TRUE(tasks.empty());
360
361 END_TEST;
362 }
363
364 } // namespace
365
366 BEGIN_TEST_CASE(scheduler_tests)
367 RUN_TEST(initial_state)
368 RUN_TEST(schedule_task)
369 RUN_TEST(ticket_obtain_finalize_without_task)
370 RUN_TEST(ticket_obtain_finalize_with_task)
371 RUN_TEST(ticket_obtain2_duplicate_finalize_release)
372 RUN_TEST(ticket_obtain2_duplicate_finalize_resume)
373 RUN_TEST(ticket_obtain2_release_finalize)
374 RUN_TEST(ticket_obtain2_resume_finalize)
375 RUN_TEST(take_all_tasks)
376 END_TEST_CASE(scheduler_tests)
377