scheduler.hh revision 13329
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
51class TraceFile;
52
53typedef NodeList<Process> ProcessList;
54typedef NodeList<Channel> ChannelList;
55
56/*
57 * The scheduler supports three different mechanisms, the initialization phase,
58 * delta cycles, and timed notifications.
59 *
60 * INITIALIZATION PHASE
61 *
62 * The initialization phase has three parts:
63 * 1. Run requested channel updates.
64 * 2. Make processes which need to initialize runnable (methods and threads
65 *    which didn't have dont_initialize called on them).
66 * 3. Process delta notifications.
67 *
68 * First, the Kernel SimObject calls the update() method during its startup()
69 * callback which handles the requested channel updates. The Kernel also
70 * schedules an event to be run at time 0 with a slightly elevated priority
71 * so that it happens before any "normal" event.
72 *
73 * When that t0 event happens, it calls the schedulers prepareForInit method
74 * which performs step 2 above. That indirectly causes the scheduler's
75 * readyEvent to be scheduled with slightly lowered priority, ensuring it
76 * happens after any "normal" event.
77 *
78 * Because delta notifications are scheduled at the standard priority, all
79 * of those events will happen next, performing step 3 above. Once they finish,
80 * if the readyEvent was scheduled above, there shouldn't be any higher
81 * priority events in front of it. When it runs, it will start the first
82 * evaluate phase of the first delta cycle.
83 *
84 * DELTA CYCLE
85 *
86 * A delta cycle has three phases within it.
87 * 1. The evaluate phase where runnable processes are allowed to run.
88 * 2. The update phase where requested channel updates hapen.
89 * 3. The delta notification phase where delta notifications happen.
90 *
91 * The readyEvent runs all three steps of the delta cycle. It first goes
92 * through the list of runnable processes and executes them until the set is
93 * empty, and then immediately runs the update phase. Since these are all part
94 * of the same event, there's no chance for other events to intervene and
95 * break the required order above.
96 *
97 * During the update phase above, the spec forbids any action which would make
98 * a process runnable. That means that once the update phase finishes, the set
99 * of runnable processes will be empty. There may, however, have been some
100 * delta notifications/timeouts which will have been scheduled during either
101 * the evaluate or update phase above. Those will have been accumulated in the
102 * scheduler, and are now all executed.
103 *
104 * If any processes became runnable during the delta notification phase, the
105 * readyEvent will have been scheduled and will be waiting and ready to run
106 * again, effectively starting the next delta cycle.
107 *
108 * TIMED NOTIFICATION PHASE
109 *
110 * If no processes became runnable, the event queue will continue to process
111 * events until it comes across an event which represents all the timed
112 * notifications which are supposed to happen at a particular time. The object
113 * which tracks them will execute all those notifications, and then destroy
114 * itself. If the readyEvent is now ready to run, the next delta cycle will
115 * start.
116 *
117 * PAUSE/STOP
118 *
119 * To inject a pause from sc_pause which should happen after the current delta
120 * cycle's delta notification phase, an event is scheduled with a lower than
121 * normal priority, but higher than the readyEvent. That ensures that any
122 * delta notifications which are scheduled with normal priority will happen
123 * first, since those are part of the current delta cycle. Then the pause
124 * event will happen before the next readyEvent which would start the next
125 * delta cycle. All of these events are scheduled for the current time, and so
126 * would happen before any timed notifications went off.
127 *
128 * To inject a stop from sc_stop, the delta cycles should stop before even the
129 * delta notifications have happened, but after the evaluate and update phases.
130 * For that, a stop event with slightly higher than normal priority will be
131 * scheduled so that it happens before any of the delta notification events
132 * which are at normal priority.
133 *
134 * MAX RUN TIME
135 *
136 * When sc_start is called, it's possible to pass in a maximum time the
137 * simulation should run to, at which point sc_pause is implicitly called. The
138 * simulation is supposed to run up to the latest timed notification phase
139 * which is less than or equal to the maximum time. In other words it should
140 * run timed notifications at the maximum time, but not the subsequent evaluate
141 * phase. That's implemented by scheduling an event at the max time with a
142 * priority which is lower than all the others except the ready event. Timed
143 * notifications will happen before it fires, but it will override any ready
144 * event and prevent the evaluate phase from starting.
145 */
146
147class Scheduler
148{
149  public:
150    typedef std::list<ScEvent *> ScEvents;
151
152    class TimeSlot : public ::Event
153    {
154      public:
155        TimeSlot() : ::Event(Default_Pri, AutoDelete) {}
156
157        ScEvents events;
158        void process();
159    };
160
161    typedef std::map<Tick, TimeSlot *> TimeSlots;
162
163    Scheduler();
164    ~Scheduler();
165
166    void clear();
167
168    const std::string name() const { return "systemc_scheduler"; }
169
170    uint64_t numCycles() { return _numCycles; }
171    Process *current() { return _current; }
172
173    void initPhase();
174
175    // Register a process with the scheduler.
176    void reg(Process *p);
177
178    // Run the next process, if there is one.
179    void yield();
180
181    // Put a process on the ready list.
182    void ready(Process *p);
183
184    // Mark a process as ready if init is finished, or put it on the list of
185    // processes to be initialized.
186    void resume(Process *p);
187
188    // Remove a process from the ready/init list if it was on one of them, and
189    // return if it was.
190    bool suspend(Process *p);
191
192    // Schedule an update for a given channel.
193    void requestUpdate(Channel *c);
194
195    // Run the given process immediately, preempting whatever may be running.
196    void
197    runNow(Process *p)
198    {
199        // This function may put a process on the wrong list, ie a thread
200        // the method list. That's fine since that's just a performance
201        // optimization, and the important thing here is how the processes are
202        // ordered.
203
204        // If a process is running, schedule it/us to run again.
205        if (_current)
206            readyListMethods.pushFirst(_current);
207        // Schedule p to run first.
208        readyListMethods.pushFirst(p);
209        yield();
210    }
211
212    // Run this process at the next opportunity.
213    void
214    runNext(Process *p)
215    {
216        // Like above, it's ok if this isn't a method. Putting it on this list
217        // just gives it priority.
218        readyListMethods.pushFirst(p);
219        if (!inEvaluate())
220            scheduleReadyEvent();
221    }
222
223    // Set an event queue for scheduling events.
224    void setEventQueue(EventQueue *_eq) { eq = _eq; }
225
226    // Get the current time according to gem5.
227    Tick getCurTick() { return eq ? eq->getCurTick() : 0; }
228
229    Tick
230    delayed(const ::sc_core::sc_time &delay)
231    {
232        return getCurTick() + delay.value();
233    }
234
235    // For scheduling delayed/timed notifications/timeouts.
236    void
237    schedule(ScEvent *event, const ::sc_core::sc_time &delay)
238    {
239        Tick tick = delayed(delay);
240        if (tick < getCurTick())
241            tick = getCurTick();
242
243        // Delta notification/timeout.
244        if (delay.value() == 0) {
245            event->schedule(deltas, tick);
246            if (!inEvaluate() && !inUpdate())
247                scheduleReadyEvent();
248            return;
249        }
250
251        // Timed notification/timeout.
252        TimeSlot *&ts = timeSlots[tick];
253        if (!ts) {
254            ts = new TimeSlot;
255            schedule(ts, tick);
256        }
257        event->schedule(ts->events, tick);
258    }
259
260    // For descheduling delayed/timed notifications/timeouts.
261    void
262    deschedule(ScEvent *event)
263    {
264        ScEvents *on = event->scheduledOn();
265
266        if (on == &deltas) {
267            event->deschedule();
268            return;
269        }
270
271        // Timed notification/timeout.
272        auto tsit = timeSlots.find(event->when());
273        panic_if(tsit == timeSlots.end(),
274                "Descheduling event at time with no events.");
275        TimeSlot *ts = tsit->second;
276        ScEvents &events = ts->events;
277        assert(on == &events);
278        event->deschedule();
279
280        // If no more events are happening at this time slot, get rid of it.
281        if (events.empty()) {
282            deschedule(ts);
283            timeSlots.erase(tsit);
284        }
285    }
286
287    void
288    completeTimeSlot(TimeSlot *ts)
289    {
290        assert(ts == timeSlots.begin()->second);
291        timeSlots.erase(timeSlots.begin());
292        if (!runToTime && starved())
293            scheduleStarvationEvent();
294        scheduleTimeAdvancesEvent();
295    }
296
297    // Pending activity ignores gem5 activity, much like how a systemc
298    // simulation wouldn't know about asynchronous external events (socket IO
299    // for instance) that might happen before time advances in a pure
300    // systemc simulation. Also the spec lists what specific types of pending
301    // activity needs to be counted, which obviously doesn't include gem5
302    // events.
303
304    // Return whether there's pending systemc activity at this time.
305    bool
306    pendingCurr()
307    {
308        return !readyListMethods.empty() || !readyListThreads.empty() ||
309            !updateList.empty() || !deltas.empty();
310    }
311
312    // Return whether there are pending timed notifications or timeouts.
313    bool
314    pendingFuture()
315    {
316        return !timeSlots.empty();
317    }
318
319    // Return how many ticks there are until the first pending event, if any.
320    Tick
321    timeToPending()
322    {
323        if (pendingCurr())
324            return 0;
325        if (pendingFuture())
326            return timeSlots.begin()->first - getCurTick();
327        return MaxTick - getCurTick();
328    }
329
330    // Run scheduled channel updates.
331    void runUpdate();
332
333    // Run delta events.
334    void runDelta();
335
336    void setScMainFiber(Fiber *sc_main) { scMain = sc_main; }
337
338    void start(Tick max_tick, bool run_to_time);
339    void oneCycle();
340
341    void schedulePause();
342    void scheduleStop(bool finish_delta);
343
344    enum Status
345    {
346        StatusOther = 0,
347        StatusEvaluate,
348        StatusUpdate,
349        StatusDelta,
350        StatusTiming,
351        StatusPaused,
352        StatusStopped
353    };
354
355    bool elaborationDone() { return _elaborationDone; }
356    void elaborationDone(bool b) { _elaborationDone = b; }
357
358    bool paused() { return status() == StatusPaused; }
359    bool stopped() { return status() == StatusStopped; }
360    bool inEvaluate() { return status() == StatusEvaluate; }
361    bool inUpdate() { return status() == StatusUpdate; }
362    bool inDelta() { return status() == StatusDelta; }
363    bool inTiming() { return status() == StatusTiming; }
364
365    uint64_t changeStamp() { return _changeStamp; }
366    void stepChangeStamp() { _changeStamp++; }
367
368    void throwToScMain();
369
370    Status status() { return _status; }
371    void status(Status s) { _status = s; }
372
373    void registerTraceFile(TraceFile *tf) { traceFiles.insert(tf); }
374    void unregisterTraceFile(TraceFile *tf) { traceFiles.erase(tf); }
375
376  private:
377    typedef const EventBase::Priority Priority;
378    static Priority DefaultPriority = EventBase::Default_Pri;
379
380    static Priority StopPriority = DefaultPriority - 1;
381    static Priority PausePriority = DefaultPriority + 1;
382    static Priority MaxTickPriority = DefaultPriority + 2;
383    static Priority ReadyPriority = DefaultPriority + 3;
384    static Priority StarvationPriority = ReadyPriority;
385    static Priority TimeAdvancesPriority = EventBase::Maximum_Pri;
386
387    EventQueue *eq;
388
389    // For gem5 style events.
390    void
391    schedule(::Event *event, Tick tick)
392    {
393        if (initDone)
394            eq->schedule(event, tick);
395        else
396            eventsToSchedule[event] = tick;
397    }
398
399    void schedule(::Event *event) { schedule(event, getCurTick()); }
400
401    void
402    deschedule(::Event *event)
403    {
404        if (initDone)
405            eq->deschedule(event);
406        else
407            eventsToSchedule.erase(event);
408    }
409
410    ScEvents deltas;
411    TimeSlots timeSlots;
412
413    Process *
414    getNextReady()
415    {
416        Process *p = readyListMethods.getNext();
417        return p ? p : readyListThreads.getNext();
418    }
419
420    void runReady();
421    EventWrapper<Scheduler, &Scheduler::runReady> readyEvent;
422    void scheduleReadyEvent();
423
424    void pause();
425    void stop();
426    EventWrapper<Scheduler, &Scheduler::pause> pauseEvent;
427    EventWrapper<Scheduler, &Scheduler::stop> stopEvent;
428
429    Fiber *scMain;
430    const ::sc_core::sc_report *_throwToScMain;
431
432    bool
433    starved()
434    {
435        return (readyListMethods.empty() && readyListThreads.empty() &&
436                updateList.empty() && deltas.empty() &&
437                (timeSlots.empty() || timeSlots.begin()->first > maxTick) &&
438                initList.empty());
439    }
440    EventWrapper<Scheduler, &Scheduler::pause> starvationEvent;
441    void scheduleStarvationEvent();
442
443    bool _elaborationDone;
444    bool _started;
445    bool _stopNow;
446
447    Status _status;
448
449    Tick maxTick;
450    Tick lastReadyTick;
451    void
452    maxTickFunc()
453    {
454        if (lastReadyTick != getCurTick())
455            _changeStamp++;
456        pause();
457    }
458    EventWrapper<Scheduler, &Scheduler::maxTickFunc> maxTickEvent;
459
460    void timeAdvances() { trace(false); }
461    EventWrapper<Scheduler, &Scheduler::timeAdvances> timeAdvancesEvent;
462    void
463    scheduleTimeAdvancesEvent()
464    {
465        if (!traceFiles.empty() && !timeAdvancesEvent.scheduled())
466            schedule(&timeAdvancesEvent);
467    }
468
469    uint64_t _numCycles;
470    uint64_t _changeStamp;
471
472    Process *_current;
473
474    bool initDone;
475    bool runToTime;
476    bool runOnce;
477
478    ProcessList initList;
479
480    ProcessList readyListMethods;
481    ProcessList readyListThreads;
482
483    ChannelList updateList;
484
485    std::map<::Event *, Tick> eventsToSchedule;
486
487    std::set<TraceFile *> traceFiles;
488
489    void trace(bool delta);
490};
491
492extern Scheduler scheduler;
493
494// A proxy function to avoid having to expose the scheduler in header files.
495Process *getCurrentProcess();
496
497inline void
498Scheduler::TimeSlot::process()
499{
500    scheduler.stepChangeStamp();
501    scheduler.status(StatusTiming);
502
503    try {
504        while (!events.empty())
505            events.front()->run();
506    } catch (...) {
507        if (events.empty())
508            scheduler.completeTimeSlot(this);
509        else
510            scheduler.schedule(this);
511        scheduler.throwToScMain();
512    }
513
514    scheduler.status(StatusOther);
515    scheduler.completeTimeSlot(this);
516}
517
518const ::sc_core::sc_report reportifyException();
519
520} // namespace sc_gem5
521
522#endif // __SYSTEMC_CORE_SCHEDULER_H__
523