systemc: Rework how delta and timed notifications/timeouts are tracked.

Rather than delegating them entirely to the gem5 event queue and using
priorities to ensure the right thing happens, this change adds a few
new structures which keep track of them and give the scheduler more
control over what happens and in what order. The old scheme was mostly
correct, but there were some competing situations which made it next
to impossible to make everything happen at the right time.

Change-Id: I43f4dd6ddfa488a31073c0318bb41369b1a6117d
Reviewed-on: https://gem5-review.googlesource.com/12213
Reviewed-by: Gabe Black <gabeblack@google.com>
Maintainer: Gabe Black <gabeblack@google.com>

7 files changed, 194 insertions, 84 deletions

diff --git a/src/systemc/core/event.cc b/src/systemc/core/event.cc
index 05670fe59..6e35da1c8 100644
--- a/src/systemc/core/event.cc
+++ b/src/systemc/core/event.cc
@@ -44,7 +44,8 @@ namespace sc_gem5
 Event::Event(sc_core::sc_event *_sc_event) : Event(_sc_event, "") {}
 
 Event::Event(sc_core::sc_event *_sc_event, const char *_basename) :
-    _sc_event(_sc_event), _basename(_basename), delayedNotifyEvent(this)
+    _sc_event(_sc_event), _basename(_basename),
+    delayedNotify([this]() { this->notify(); })
 {
     Module *p = currentModule();
 
@@ -90,8 +91,8 @@ Event::~Event()
     std::swap(*it, allEvents.back());
     allEvents.pop_back();
 
-    if (delayedNotifyEvent.scheduled())
-        scheduler.deschedule(&delayedNotifyEvent);
+    if (delayedNotify.scheduled())
+        scheduler.deschedule(&delayedNotify);
 }
 
 const std::string &
@@ -127,34 +128,22 @@ Event::notify()
 }
 
 void
-Event::delayedNotify()
-{
-    scheduler.eventHappened();
-    notify();
-}
-
-void
 Event::notify(const sc_core::sc_time &t)
 {
-    //XXX We're assuming the systemc time resolution is in ps.
-    Tick new_tick = t.value() * SimClock::Int::ps + scheduler.getCurTick();
-    if (delayedNotifyEvent.scheduled()) {
-        Tick old_tick = delayedNotifyEvent.when();
-
-        if (new_tick >= old_tick)
+    if (delayedNotify.scheduled()) {
+        if (scheduler.delayed(t) >= delayedNotify.when())
             return;
 
-        scheduler.deschedule(&delayedNotifyEvent);
+        scheduler.deschedule(&delayedNotify);
     }
-
-    scheduler.schedule(&delayedNotifyEvent, new_tick);
+    scheduler.schedule(&delayedNotify, t);
 }
 
 void
 Event::cancel()
 {
-    if (delayedNotifyEvent.scheduled())
-        scheduler.deschedule(&delayedNotifyEvent);
+    if (delayedNotify.scheduled())
+        scheduler.deschedule(&delayedNotify);
 }
 
 bool
diff --git a/src/systemc/core/event.hh b/src/systemc/core/event.hh
index f9d3b2040..57d3f3f6f 100644
--- a/src/systemc/core/event.hh
+++ b/src/systemc/core/event.hh
@@ -37,6 +37,7 @@
 #include "sim/eventq.hh"
 #include "systemc/core/list.hh"
 #include "systemc/core/object.hh"
+#include "systemc/core/sched_event.hh"
 #include "systemc/ext/core/sc_prim.hh"
 #include "systemc/ext/core/sc_time.hh"
 
@@ -104,8 +105,7 @@ class Event
 
     sc_core::sc_object *parent;
 
-    void delayedNotify();
-    EventWrapper<Event, &Event::delayedNotify> delayedNotifyEvent;
+    ScEvent delayedNotify;
 
     mutable std::set<Sensitivity *> sensitivities;
 };
diff --git a/src/systemc/core/process.cc b/src/systemc/core/process.cc
index ef1cea61a..3e629c3ec 100644
--- a/src/systemc/core/process.cc
+++ b/src/systemc/core/process.cc
@@ -39,10 +39,9 @@ namespace sc_gem5
 {
 
 SensitivityTimeout::SensitivityTimeout(Process *p, ::sc_core::sc_time t) :
-    Sensitivity(p), timeoutEvent(this), time(t)
+    Sensitivity(p), timeoutEvent([this]() { this->timeout(); })
 {
-    Tick when = scheduler.getCurTick() + time.value();
-    scheduler.schedule(&timeoutEvent, when);
+    scheduler.schedule(&timeoutEvent, t);
 }
 
 SensitivityTimeout::~SensitivityTimeout()
@@ -54,7 +53,6 @@ SensitivityTimeout::~SensitivityTimeout()
 void
 SensitivityTimeout::timeout()
 {
-    scheduler.eventHappened();
     notify();
 }
 
diff --git a/src/systemc/core/process.hh b/src/systemc/core/process.hh
index 33dcf870d..25d3e4eb0 100644
--- a/src/systemc/core/process.hh
+++ b/src/systemc/core/process.hh
@@ -39,6 +39,7 @@
 #include "systemc/core/bindinfo.hh"
 #include "systemc/core/list.hh"
 #include "systemc/core/object.hh"
+#include "systemc/core/sched_event.hh"
 #include "systemc/ext/core/sc_event.hh"
 #include "systemc/ext/core/sc_export.hh"
 #include "systemc/ext/core/sc_interface.hh"
@@ -70,9 +71,7 @@ class SensitivityTimeout : virtual public Sensitivity
 {
   private:
     void timeout();
-    EventWrapper<SensitivityTimeout,
-        &SensitivityTimeout::timeout> timeoutEvent;
-    ::sc_core::sc_time time;
+    ScEvent timeoutEvent;
 
   public:
     SensitivityTimeout(Process *p, ::sc_core::sc_time t);
diff --git a/src/systemc/core/sched_event.hh b/src/systemc/core/sched_event.hh
new file mode 100644
index 000000000..63b76ef0a
--- /dev/null
+++ b/src/systemc/core/sched_event.hh
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2018 Google, Inc.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Gabe Black
+ */
+
+#ifndef __SYSTEMC_CORE_SCHED_EVENT_HH__
+#define __SYSTEMC_CORE_SCHED_EVENT_HH__
+
+#include <functional>
+
+#include "base/types.hh"
+
+namespace sc_gem5
+{
+
+class ScEvent
+{
+  private:
+    std::function<void()> work;
+    Tick _when;
+    bool _scheduled;
+
+    friend class Scheduler;
+
+    void
+    schedule(Tick w)
+    {
+        when(w);
+        _scheduled = true;
+    }
+
+    void deschedule() { _scheduled = false; }
+  public:
+    ScEvent(std::function<void()> work) :
+        work(work), _when(MaxTick), _scheduled(false)
+    {}
+
+    bool scheduled() { return _scheduled; }
+
+    void when(Tick w) { _when = w; }
+    Tick when() { return _when; }
+
+    void run() { deschedule(); work(); }
+};
+
+} // namespace sc_gem5
+
+#endif // __SYSTEMC_CORE_SCHED_EVENT_HH__
diff --git a/src/systemc/core/scheduler.cc b/src/systemc/core/scheduler.cc
index 7e5272d0e..bc08d5556 100644
--- a/src/systemc/core/scheduler.cc
+++ b/src/systemc/core/scheduler.cc
@@ -191,7 +191,10 @@ Scheduler::runReady()
     if (starved() && !runToTime)
         scheduleStarvationEvent();
 
-    // The delta phase will happen naturally through the event queue.
+    // The delta phase.
+    for (auto &e: deltas)
+        e->run();
+    deltas.clear();
 
     if (runOnce) {
         eq->reschedule(&maxTickEvent, eq->getCurTick());
diff --git a/src/systemc/core/scheduler.hh b/src/systemc/core/scheduler.hh
index 661a36b78..b221e67d9 100644
--- a/src/systemc/core/scheduler.hh
+++ b/src/systemc/core/scheduler.hh
@@ -30,13 +30,18 @@
 #ifndef __SYSTEMC_CORE_SCHEDULER_HH__
 #define __SYSTEMC_CORE_SCHEDULER_HH__
 
+#include <functional>
+#include <map>
+#include <set>
 #include <vector>
 
 #include "base/logging.hh"
+#include "sim/core.hh"
 #include "sim/eventq.hh"
 #include "systemc/core/channel.hh"
 #include "systemc/core/list.hh"
 #include "systemc/core/process.hh"
+#include "systemc/core/sched_event.hh"
 
 class Fiber;
 
@@ -81,7 +86,7 @@ typedef NodeList<Channel> ChannelList;
  * 2. The update phase where requested channel updates hapen.
  * 3. The delta notification phase where delta notifications happen.
  *
- * The readyEvent runs the first two steps of the delta cycle. It first goes
+ * The readyEvent runs all three steps of the delta cycle. It first goes
  * through the list of runnable processes and executes them until the set is
  * empty, and then immediately runs the update phase. Since these are all part
  * of the same event, there's no chance for other events to intervene and
@@ -91,23 +96,21 @@ typedef NodeList<Channel> ChannelList;
  * a process runnable. That means that once the update phase finishes, the set
  * of runnable processes will be empty. There may, however, have been some
  * delta notifications/timeouts which will have been scheduled during either
- * the evaluate or update phase above. Because those are scheduled at the
- * normal priority, they will now happen together until there aren't any
- * delta events left.
+ * the evaluate or update phase above. Those will have been accumulated in the
+ * scheduler, and are now all executed.
  *
  * If any processes became runnable during the delta notification phase, the
- * readyEvent will have been scheduled and will have been waiting patiently
- * behind the delta notification events. That will now run, effectively
- * starting the next delta cycle.
+ * readyEvent will have been scheduled and will be waiting and ready to run
+ * again, effectively starting the next delta cycle.
  *
  * TIMED NOTIFICATION PHASE
  *
  * If no processes became runnable, the event queue will continue to process
- * events until it comes across a timed notification, aka a notification
- * scheduled to happen in the future. Like delta notification events, those
- * will all happen together since the readyEvent priority is lower,
- * potentially marking new processes as ready. Once these events finish, the
- * readyEvent may run, starting the next delta cycle.
+ * events until it comes across an event which represents all the timed
+ * notifications which are supposed to happen at a particular time. The object
+ * which tracks them will execute all those notifications, and then destroy
+ * itself. If the readyEvent is now ready to run, the next delta cycle will
+ * start.
  *
  * PAUSE/STOP
  *
@@ -142,6 +145,19 @@ typedef NodeList<Channel> ChannelList;
 class Scheduler
 {
   public:
+    typedef std::set<ScEvent *> ScEvents;
+
+    class TimeSlot : public ::Event
+    {
+      public:
+        TimeSlot() : ::Event(Default_Pri, AutoDelete) {}
+
+        ScEvents events;
+        void process();
+    };
+
+    typedef std::map<Tick, TimeSlot *> TimeSlots;
+
     Scheduler();
 
     const std::string name() const { return "systemc_scheduler"; }
@@ -185,42 +201,74 @@ class Scheduler
     // Get the current time according to gem5.
     Tick getCurTick() { return eq ? eq->getCurTick() : 0; }
 
+    Tick
+    delayed(const ::sc_core::sc_time &delay)
+    {
+        //XXX We're assuming the systemc time resolution is in ps.
+        return getCurTick() + delay.value() * SimClock::Int::ps;
+    }
+
     // For scheduling delayed/timed notifications/timeouts.
     void
-    schedule(::Event *event, Tick tick)
+    schedule(ScEvent *event, const ::sc_core::sc_time &delay)
     {
-        pendingTicks[tick]++;
+        Tick tick = delayed(delay);
+        event->schedule(tick);
+
+        // Delta notification/timeout.
+        if (delay.value() == 0) {
+            deltas.insert(event);
+            scheduleReadyEvent();
+            return;
+        }
 
-        if (initReady)
-            eq->schedule(event, tick);
-        else
-            eventsToSchedule[event] = tick;
+        // Timed notification/timeout.
+        TimeSlot *&ts = timeSlots[tick];
+        if (!ts) {
+            ts = new TimeSlot;
+            if (initReady)
+                eq->schedule(ts, tick);
+            else
+                eventsToSchedule[ts] = tick;
+        }
+        ts->events.insert(event);
     }
 
     // For descheduling delayed/timed notifications/timeouts.
     void
-    deschedule(::Event *event)
+    deschedule(ScEvent *event)
     {
-        auto it = pendingTicks.find(event->when());
-        if (--it->second == 0)
-            pendingTicks.erase(it);
-
-        if (initReady)
-            eq->deschedule(event);
-        else
-            eventsToSchedule.erase(event);
+        if (event->when() == getCurTick()) {
+            // Remove from delta notifications.
+            deltas.erase(event);
+            event->deschedule();
+            return;
+        }
+
+        // Timed notification/timeout.
+        auto tsit = timeSlots.find(event->when());
+        panic_if(tsit == timeSlots.end(),
+                "Descheduling event at time with no events.");
+        TimeSlot *ts = tsit->second;
+        ScEvents &events = ts->events;
+        events.erase(event);
+        event->deschedule();
+
+        // If no more events are happening at this time slot, get rid of it.
+        if (events.empty()) {
+            if (initReady)
+                eq->deschedule(ts);
+            else
+                eventsToSchedule.erase(ts);
+            timeSlots.erase(tsit);
+        }
     }
 
-    // Tell the scheduler than an event fired for bookkeeping purposes.
     void
-    eventHappened()
+    completeTimeSlot(TimeSlot *ts)
     {
-        auto it = pendingTicks.begin();
-        if (--it->second == 0)
-            pendingTicks.erase(it);
-
-        if (starved() && !runToTime)
-            scheduleStarvationEvent();
+        assert(ts == timeSlots.begin()->second);
+        timeSlots.erase(timeSlots.begin());
     }
 
     // Pending activity ignores gem5 activity, much like how a systemc
@@ -234,33 +282,25 @@ class Scheduler
     bool
     pendingCurr()
     {
-        if (!readyList.empty() || !updateList.empty())
-            return true;
-        return pendingTicks.size() &&
-            pendingTicks.begin()->first == getCurTick();
+        return !readyList.empty() || !updateList.empty() || !deltas.empty();
     }
 
     // Return whether there are pending timed notifications or timeouts.
     bool
     pendingFuture()
     {
-        switch (pendingTicks.size()) {
-          case 0: return false;
-          case 1: return pendingTicks.begin()->first > getCurTick();
-          default: return true;
-        }
+        return !timeSlots.empty();
     }
 
     // Return how many ticks there are until the first pending event, if any.
     Tick
     timeToPending()
     {
-        if (!readyList.empty() || !updateList.empty())
+        if (pendingCurr())
             return 0;
-        else if (pendingTicks.size())
-            return pendingTicks.begin()->first - getCurTick();
-        else
-            return MaxTick - getCurTick();
+        if (pendingFuture())
+            return timeSlots.begin()->first - getCurTick();
+        return MaxTick - getCurTick();
     }
 
     // Run scheduled channel updates.
@@ -288,7 +328,9 @@ class Scheduler
     static Priority StarvationPriority = ReadyPriority;
 
     EventQueue *eq;
-    std::map<Tick, int> pendingTicks;
+
+    ScEvents deltas;
+    TimeSlots timeSlots;
 
     void runReady();
     EventWrapper<Scheduler, &Scheduler::runReady> readyEvent;
@@ -303,9 +345,8 @@ class Scheduler
     bool
     starved()
     {
-        return (readyList.empty() && updateList.empty() &&
-                (pendingTicks.empty() ||
-                 pendingTicks.begin()->first > maxTick) &&
+        return (readyList.empty() && updateList.empty() && deltas.empty() &&
+                (timeSlots.empty() || timeSlots.begin()->first > maxTick) &&
                 initList.empty());
     }
     EventWrapper<Scheduler, &Scheduler::pause> starvationEvent;
@@ -337,6 +378,14 @@ class Scheduler
 
 extern Scheduler scheduler;
 
+inline void
+Scheduler::TimeSlot::process()
+{
+    for (auto &e: events)
+        e->run();
+    scheduler.completeTimeSlot(this);
+}
+
 } // namespace sc_gem5
 
 #endif // __SYSTEMC_CORE_SCHEDULER_H__