scheduler.hh revision 13188
1/*
2 * Copyright 2018 Google, Inc.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met: redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer;
8 * redistributions in binary form must reproduce the above copyright
9 * notice, this list of conditions and the following disclaimer in the
10 * documentation and/or other materials provided with the distribution;
11 * neither the name of the copyright holders nor the names of its
12 * contributors may be used to endorse or promote products derived from
13 * this software without specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 * Authors: Gabe Black
28 */
29
30#ifndef __SYSTEMC_CORE_SCHEDULER_HH__
31#define __SYSTEMC_CORE_SCHEDULER_HH__
32
33#include <functional>
34#include <map>
35#include <set>
36#include <vector>
37
38#include "base/logging.hh"
39#include "sim/core.hh"
40#include "sim/eventq.hh"
41#include "systemc/core/channel.hh"
42#include "systemc/core/list.hh"
43#include "systemc/core/process.hh"
44#include "systemc/core/sched_event.hh"
45
46class Fiber;
47
48namespace sc_gem5
49{
50
51typedef NodeList<Process> ProcessList;
52typedef NodeList<Channel> ChannelList;
53
54/*
55 * The scheduler supports three different mechanisms, the initialization phase,
56 * delta cycles, and timed notifications.
57 *
58 * INITIALIZATION PHASE
59 *
60 * The initialization phase has three parts:
61 * 1. Run requested channel updates.
62 * 2. Make processes which need to initialize runnable (methods and threads
63 *    which didn't have dont_initialize called on them).
64 * 3. Process delta notifications.
65 *
66 * First, the Kernel SimObject calls the update() method during its startup()
67 * callback which handles the requested channel updates. The Kernel also
68 * schedules an event to be run at time 0 with a slightly elevated priority
69 * so that it happens before any "normal" event.
70 *
71 * When that t0 event happens, it calls the schedulers prepareForInit method
72 * which performs step 2 above. That indirectly causes the scheduler's
73 * readyEvent to be scheduled with slightly lowered priority, ensuring it
74 * happens after any "normal" event.
75 *
76 * Because delta notifications are scheduled at the standard priority, all
77 * of those events will happen next, performing step 3 above. Once they finish,
78 * if the readyEvent was scheduled above, there shouldn't be any higher
79 * priority events in front of it. When it runs, it will start the first
80 * evaluate phase of the first delta cycle.
81 *
82 * DELTA CYCLE
83 *
84 * A delta cycle has three phases within it.
85 * 1. The evaluate phase where runnable processes are allowed to run.
86 * 2. The update phase where requested channel updates hapen.
87 * 3. The delta notification phase where delta notifications happen.
88 *
89 * The readyEvent runs all three steps of the delta cycle. It first goes
90 * through the list of runnable processes and executes them until the set is
91 * empty, and then immediately runs the update phase. Since these are all part
92 * of the same event, there's no chance for other events to intervene and
93 * break the required order above.
94 *
95 * During the update phase above, the spec forbids any action which would make
96 * a process runnable. That means that once the update phase finishes, the set
97 * of runnable processes will be empty. There may, however, have been some
98 * delta notifications/timeouts which will have been scheduled during either
99 * the evaluate or update phase above. Those will have been accumulated in the
100 * scheduler, and are now all executed.
101 *
102 * If any processes became runnable during the delta notification phase, the
103 * readyEvent will have been scheduled and will be waiting and ready to run
104 * again, effectively starting the next delta cycle.
105 *
106 * TIMED NOTIFICATION PHASE
107 *
108 * If no processes became runnable, the event queue will continue to process
109 * events until it comes across an event which represents all the timed
110 * notifications which are supposed to happen at a particular time. The object
111 * which tracks them will execute all those notifications, and then destroy
112 * itself. If the readyEvent is now ready to run, the next delta cycle will
113 * start.
114 *
115 * PAUSE/STOP
116 *
117 * To inject a pause from sc_pause which should happen after the current delta
118 * cycle's delta notification phase, an event is scheduled with a lower than
119 * normal priority, but higher than the readyEvent. That ensures that any
120 * delta notifications which are scheduled with normal priority will happen
121 * first, since those are part of the current delta cycle. Then the pause
122 * event will happen before the next readyEvent which would start the next
123 * delta cycle. All of these events are scheduled for the current time, and so
124 * would happen before any timed notifications went off.
125 *
126 * To inject a stop from sc_stop, the delta cycles should stop before even the
127 * delta notifications have happened, but after the evaluate and update phases.
128 * For that, a stop event with slightly higher than normal priority will be
129 * scheduled so that it happens before any of the delta notification events
130 * which are at normal priority.
131 *
132 * MAX RUN TIME
133 *
134 * When sc_start is called, it's possible to pass in a maximum time the
135 * simulation should run to, at which point sc_pause is implicitly called. The
136 * simulation is supposed to run up to the latest timed notification phase
137 * which is less than or equal to the maximum time. In other words it should
138 * run timed notifications at the maximum time, but not the subsequent evaluate
139 * phase. That's implemented by scheduling an event at the max time with a
140 * priority which is lower than all the others except the ready event. Timed
141 * notifications will happen before it fires, but it will override any ready
142 * event and prevent the evaluate phase from starting.
143 */
144
145class Scheduler
146{
147  public:
148    typedef std::list<ScEvent *> ScEvents;
149
150    class TimeSlot : public ::Event
151    {
152      public:
153        TimeSlot() : ::Event(Default_Pri, AutoDelete) {}
154
155        ScEvents events;
156        void process();
157    };
158
159    typedef std::map<Tick, TimeSlot *> TimeSlots;
160
161    Scheduler();
162    ~Scheduler();
163
164    void clear();
165
166    const std::string name() const { return "systemc_scheduler"; }
167
168    uint64_t numCycles() { return _numCycles; }
169    Process *current() { return _current; }
170
171    void initPhase();
172
173    // Register a process with the scheduler.
174    void reg(Process *p);
175
176    // Tell the scheduler not to initialize a process.
177    void dontInitialize(Process *p);
178
179    // Run the next process, if there is one.
180    void yield();
181
182    // Put a process on the ready list.
183    void ready(Process *p);
184
185    // Mark a process as ready if init is finished, or put it on the list of
186    // processes to be initialized.
187    void resume(Process *p);
188
189    // Remove a process from the ready/init list if it was on one of them, and
190    // return if it was.
191    bool suspend(Process *p);
192
193    // Schedule an update for a given channel.
194    void requestUpdate(Channel *c);
195
196    // Run the given process immediately, preempting whatever may be running.
197    void
198    runNow(Process *p)
199    {
200        // This function may put a process on the wrong list, ie a method on
201        // the process list or vice versa. That's fine since that's just a
202        // performance optimization, and the important thing here is how the
203        // processes are ordered.
204
205        // If a process is running, schedule it/us to run again.
206        if (_current)
207            readyList->pushFirst(_current);
208        // Schedule p to run first.
209        readyList->pushFirst(p);
210        yield();
211    }
212
213    // Set an event queue for scheduling events.
214    void setEventQueue(EventQueue *_eq) { eq = _eq; }
215
216    // Get the current time according to gem5.
217    Tick getCurTick() { return eq ? eq->getCurTick() : 0; }
218
219    Tick
220    delayed(const ::sc_core::sc_time &delay)
221    {
222        //XXX We're assuming the systemc time resolution is in ps.
223        return getCurTick() + delay.value() * SimClock::Int::ps;
224    }
225
226    // For scheduling delayed/timed notifications/timeouts.
227    void
228    schedule(ScEvent *event, const ::sc_core::sc_time &delay)
229    {
230        Tick tick = delayed(delay);
231        if (tick < getCurTick())
232            tick = getCurTick();
233
234        // Delta notification/timeout.
235        if (delay.value() == 0) {
236            event->schedule(deltas, tick);
237            scheduleReadyEvent();
238            return;
239        }
240
241        // Timed notification/timeout.
242        TimeSlot *&ts = timeSlots[tick];
243        if (!ts) {
244            ts = new TimeSlot;
245            schedule(ts, tick);
246        }
247        event->schedule(ts->events, tick);
248    }
249
250    // For descheduling delayed/timed notifications/timeouts.
251    void
252    deschedule(ScEvent *event)
253    {
254        ScEvents *on = event->scheduledOn();
255
256        if (on == &deltas) {
257            event->deschedule();
258            return;
259        }
260
261        // Timed notification/timeout.
262        auto tsit = timeSlots.find(event->when());
263        panic_if(tsit == timeSlots.end(),
264                "Descheduling event at time with no events.");
265        TimeSlot *ts = tsit->second;
266        ScEvents &events = ts->events;
267        assert(on == &events);
268        event->deschedule();
269
270        // If no more events are happening at this time slot, get rid of it.
271        if (events.empty()) {
272            deschedule(ts);
273            timeSlots.erase(tsit);
274        }
275    }
276
277    void
278    completeTimeSlot(TimeSlot *ts)
279    {
280        _changeStamp++;
281        assert(ts == timeSlots.begin()->second);
282        timeSlots.erase(timeSlots.begin());
283        if (!runToTime && starved())
284            scheduleStarvationEvent();
285    }
286
287    // Pending activity ignores gem5 activity, much like how a systemc
288    // simulation wouldn't know about asynchronous external events (socket IO
289    // for instance) that might happen before time advances in a pure
290    // systemc simulation. Also the spec lists what specific types of pending
291    // activity needs to be counted, which obviously doesn't include gem5
292    // events.
293
294    // Return whether there's pending systemc activity at this time.
295    bool
296    pendingCurr()
297    {
298        return !readyListMethods.empty() || !readyListThreads.empty() ||
299            !updateList.empty() || !deltas.empty();
300    }
301
302    // Return whether there are pending timed notifications or timeouts.
303    bool
304    pendingFuture()
305    {
306        return !timeSlots.empty();
307    }
308
309    // Return how many ticks there are until the first pending event, if any.
310    Tick
311    timeToPending()
312    {
313        if (pendingCurr())
314            return 0;
315        if (pendingFuture())
316            return timeSlots.begin()->first - getCurTick();
317        return MaxTick - getCurTick();
318    }
319
320    // Run scheduled channel updates.
321    void runUpdate();
322
323    // Run delta events.
324    void runDelta();
325
326    void setScMainFiber(Fiber *sc_main) { scMain = sc_main; }
327
328    void start(Tick max_tick, bool run_to_time);
329    void oneCycle();
330
331    void schedulePause();
332    void scheduleStop(bool finish_delta);
333
334    enum Status
335    {
336        StatusOther = 0,
337        StatusDelta,
338        StatusUpdate,
339        StatusTiming,
340        StatusPaused,
341        StatusStopped
342    };
343
344    bool paused() { return status() == StatusPaused; }
345    bool stopped() { return status() == StatusStopped; }
346    bool inDelta() { return status() == StatusDelta; }
347    bool inUpdate() { return status() == StatusUpdate; }
348    bool inTiming() { return status() == StatusTiming; }
349
350    uint64_t changeStamp() { return _changeStamp; }
351
352    void throwToScMain(const ::sc_core::sc_report *r=nullptr);
353
354    Status status() { return _status; }
355    void status(Status s) { _status = s; }
356
357  private:
358    typedef const EventBase::Priority Priority;
359    static Priority DefaultPriority = EventBase::Default_Pri;
360
361    static Priority StopPriority = DefaultPriority - 1;
362    static Priority PausePriority = DefaultPriority + 1;
363    static Priority MaxTickPriority = DefaultPriority + 2;
364    static Priority ReadyPriority = DefaultPriority + 3;
365    static Priority StarvationPriority = ReadyPriority;
366
367    EventQueue *eq;
368
369    // For gem5 style events.
370    void
371    schedule(::Event *event, Tick tick)
372    {
373        if (initDone)
374            eq->schedule(event, tick);
375        else
376            eventsToSchedule[event] = tick;
377    }
378
379    void schedule(::Event *event) { schedule(event, getCurTick()); }
380
381    void
382    deschedule(::Event *event)
383    {
384        if (initDone)
385            eq->deschedule(event);
386        else
387            eventsToSchedule.erase(event);
388    }
389
390    ScEvents deltas;
391    TimeSlots timeSlots;
392
393    void runReady();
394    EventWrapper<Scheduler, &Scheduler::runReady> readyEvent;
395    void scheduleReadyEvent();
396
397    void pause();
398    void stop();
399    EventWrapper<Scheduler, &Scheduler::pause> pauseEvent;
400    EventWrapper<Scheduler, &Scheduler::stop> stopEvent;
401
402    Fiber *scMain;
403    const ::sc_core::sc_report *_throwToScMain;
404
405    bool
406    starved()
407    {
408        return (readyListMethods.empty() && readyListThreads.empty() &&
409                updateList.empty() && deltas.empty() &&
410                (timeSlots.empty() || timeSlots.begin()->first > maxTick) &&
411                initList.empty());
412    }
413    EventWrapper<Scheduler, &Scheduler::pause> starvationEvent;
414    void scheduleStarvationEvent();
415
416    bool _started;
417    bool _stopNow;
418
419    Status _status;
420
421    Tick maxTick;
422    Tick lastReadyTick;
423    void
424    maxTickFunc()
425    {
426        if (lastReadyTick != getCurTick())
427            _changeStamp++;
428        pause();
429    }
430    EventWrapper<Scheduler, &Scheduler::maxTickFunc> maxTickEvent;
431
432    uint64_t _numCycles;
433    uint64_t _changeStamp;
434
435    Process *_current;
436
437    bool initDone;
438    bool runToTime;
439    bool runOnce;
440
441    ProcessList initList;
442    ProcessList toFinalize;
443
444    ProcessList *readyList;
445    ProcessList readyListMethods;
446    ProcessList readyListThreads;
447
448    ChannelList updateList;
449
450    std::map<::Event *, Tick> eventsToSchedule;
451};
452
453extern Scheduler scheduler;
454
455inline void
456Scheduler::TimeSlot::process()
457{
458    scheduler.status(StatusTiming);
459
460    try {
461        while (!events.empty())
462            events.front()->run();
463    } catch (...) {
464        if (events.empty())
465            scheduler.completeTimeSlot(this);
466        else
467            scheduler.schedule(this);
468        scheduler.throwToScMain();
469    }
470
471    scheduler.status(StatusOther);
472    scheduler.completeTimeSlot(this);
473}
474
475const ::sc_core::sc_report *reportifyException();
476
477} // namespace sc_gem5
478
479#endif // __SYSTEMC_CORE_SCHEDULER_H__
480