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 #ifndef LIB_FIT_SCHEDULER_H_
6 #define LIB_FIT_SCHEDULER_H_
7 
8 #include <map>
9 #include <queue>
10 #include <utility>
11 
12 #include "promise.h"
13 
14 namespace fit {
15 namespace subtle {
16 
17 // Keeps track of runnable and suspended tasks.
18 // This is a low-level building block for implementing executors.
19 // For a concrete implementation, see |fit::single_threaded_executor|.
20 //
21 // Instances of this object are not thread-safe.  Its client is responsible
22 // for providing all necessary synchronization.
23 class scheduler final {
24 public:
25     using task_queue = std::queue<pending_task>;
26     using ref_count = uint32_t;
27 
28     scheduler();
29     ~scheduler();
30 
31     // Adds a task to the runnable queue.
32     //
33     // Preconditions:
34     // - |task| must be non-empty
35     void schedule_task(pending_task task);
36 
37     // Obtains a new ticket with a ref-count of |initial_refs|.
38     // The executor must eventually call |finalize_ticket()| to update the
39     // state of the ticket.
40     //
41     // Preconditions:
42     // - |initial_refs| must be at least 1
43     suspended_task::ticket obtain_ticket(ref_count initial_refs = 1);
44 
45     // Updates a ticket after one run of a task's continuation according
46     // to the state of the task after its run.  The executor must call this
47     // method after calling |obtain_ticket()| to indicate the disposition of
48     // the task for which the ticket was obtained.
49     //
50     // Passing an empty |task| indicates that the task has completed so it
51     // does not need to be resumed.
52     //
53     // Passing a non-empty |task| indicates that the task returned a pending
54     // result and may need to be suspended depending on the current state
55     // of the ticket.
56     // - If the ticket has already been resumed, moves |task| into the
57     //   runnable queue.
58     // - Otherwise, if the ticket still has a non-zero ref-count, moves |task|
59     //   into the suspended task table.
60     // - Otherwise, considers the task abandoned and the caller retains
61     //   ownership of |task|.
62     //
63     // Preconditions:
64     // - |task| must be non-null (may be empty)
65     // - the ticket must not have already been finalized
66     void finalize_ticket(suspended_task::ticket ticket, pending_task* task);
67 
68     // Increments the ticket's ref-count.
69     //
70     // Preconditions:
71     // - the ticket's ref-count must be non-zero (positive)
72     void duplicate_ticket(suspended_task::ticket ticket);
73 
74     // Decrements the ticket's ref-count.
75     //
76     // If the task's ref-count reaches 0 and has an associated task that
77     // has not already been resumed, returns the associated task back
78     // to the caller.
79     // Otherwise, returns an empty task.
80     //
81     // Preconditions:
82     // - the ticket's ref-count must be non-zero (positive)
83     pending_task release_ticket(suspended_task::ticket ticket);
84 
85     // Resumes a task and decrements the ticket's ref-count.
86     //
87     // If the ticket has an associated task that has not already been resumed,
88     // moves its associated task to the runnable queue and returns true.
89     // Otherwise, returns false.
90     //
91     // Preconditions:
92     // - the ticket's ref-count must be non-zero (positive)
93     bool resume_task_with_ticket(suspended_task::ticket ticket);
94 
95     // Takes all tasks in the runnable queue.
96     //
97     // Preconditions:
98     // - |tasks| must be non-null and empty
99     void take_runnable_tasks(task_queue* tasks);
100 
101     // Takes all remaining tasks, regardless of whether they are runnable
102     // or suspended.
103     //
104     // This operation is useful when shutting down an executor.
105     //
106     // Preconditions:
107     // - |tasks| must be non-null and empty
108     void take_all_tasks(task_queue* tasks);
109 
110     // Returns true if there are any runnable tasks.
has_runnable_tasks()111     bool has_runnable_tasks() const { return !runnable_tasks_.empty(); }
112 
113     // Returns true if there are any suspended tasks that have yet to
114     // be resumed.
has_suspended_tasks()115     bool has_suspended_tasks() const { return suspended_task_count_ > 0; }
116 
117     // Returns true if there are any tickets that have yet to be finalized,
118     // released, or resumed.
has_outstanding_tickets()119     bool has_outstanding_tickets() const { return !tickets_.empty(); }
120 
121     scheduler(const scheduler&) = delete;
122     scheduler(scheduler&&) = delete;
123     scheduler& operator=(const scheduler&) = delete;
124     scheduler& operator=(scheduler&&) = delete;
125 
126 private:
127     struct ticket_record {
ticket_recordticket_record128         ticket_record(ref_count initial_refs)
129             : ref_count(initial_refs), was_resumed(false) {}
130 
131         // The current reference count.
132         ref_count ref_count;
133 
134         // True if the task has been resumed using |resume_task_with_ticket()|.
135         bool was_resumed;
136 
137         // The task is initially empty when the ticket is obtained.
138         // It is later set to non-empty if the task needs to be suspended when
139         // the ticket is finalized.  It becomes empty again when the task
140         // is moved into the runnable queue, released, or taken.
141         pending_task task;
142     };
143     using ticket_map = std::map<suspended_task::ticket, ticket_record>;
144 
145     task_queue runnable_tasks_;
146     ticket_map tickets_;
147     uint64_t suspended_task_count_ = 0;
148     suspended_task::ticket next_ticket_ = 1;
149 };
150 
151 } // namespace subtle
152 } // namespace fit
153 
154 #endif // LIB_FIT_SCHEDULER_H_
155