X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fsim%2Feventq.hh;h=e0194a742e6f2b1b6b428ff9e3f7dfdbfec03034;hb=eb89a23556a16958d9931b93f57b626f20af0ddd;hp=ea950e625b0c002f56ae9e84a94de6eddab6304c;hpb=93517dd90cf232b779beeebb162984d543e7e33c;p=gem5.git diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh index ea950e625..e0194a742 100644 --- a/src/sim/eventq.hh +++ b/src/sim/eventq.hh @@ -38,6 +38,7 @@ #include #include +#include #include #include #include @@ -48,7 +49,7 @@ #include "sim/serialize.hh" #include "sim/host.hh" -class EventQueue; // forward declaration +class EventQueue; // forward declaration ////////////////////// // @@ -74,14 +75,27 @@ class Event : public Serializable, public FastAlloc friend class EventQueue; private: - Event *next; + // The event queue is now a linked list of linked lists. The + // 'nextBin' pointer is to find the bin, where a bin is defined as + // when+priority. All events in the same bin will be stored in a + // second linked list (a stack) maintained by the 'nextInBin' + // pointer. The list will be accessed in LIFO order. The end + // result is that the insert/removal in 'nextBin' is + // linear/constant, and the lookup/removal in 'nextInBin' is + // constant/constant. Hopefully this is a significant improvement + // over the current fully linear insertion. + Event *nextBin; + Event *nextInBin; + + static Event *insertBefore(Event *event, Event *curr); + static Event *removeItem(Event *event, Event *last); /// queue to which this event belongs (though it may or may not be /// scheduled on this queue yet) EventQueue *_queue; - Tick _when; //!< timestamp when event should be processed - short _priority; //!< event priority + Tick _when; //!< timestamp when event should be processed + short _priority; //!< event priority short _flags; #ifndef NDEBUG @@ -95,10 +109,21 @@ class Event : public Serializable, public FastAlloc Counter instance; #endif -#ifdef DEBUG_EVENTQ +#ifdef EVENTQ_DEBUG Tick whenCreated; //!< time created Tick whenScheduled; //!< time scheduled #endif + + protected: + void + setWhen(Tick when) + { + _when = when; +#ifdef EVENTQ_DEBUG + whenScheduled = curTick; +#endif + } + protected: enum Flags { None = 0x0, @@ -117,7 +142,7 @@ class Event : public Serializable, public FastAlloc EventQueue *queue() const { return _queue; } // This function isn't really useful if TRACING_ON is not defined - virtual void trace(const char *action); //!< trace event activity + virtual void trace(const char *action); //!< trace event activity public: /// Event priorities, to provide tie-breakers for events scheduled @@ -126,7 +151,7 @@ class Event : public Serializable, public FastAlloc /// be ordered within a cycle. enum Priority { /// Minimum priority - Minimum_Pri = SHRT_MIN, + Minimum_Pri = SHRT_MIN, /// If we enable tracing on a particular cycle, do that as the /// very first thing so we don't miss any of the events on @@ -136,44 +161,44 @@ class Event : public Serializable, public FastAlloc /// Breakpoints should happen before anything else (except /// enabling trace output), so we don't miss any action when /// debugging. - Debug_Break_Pri = -100, + Debug_Break_Pri = -100, /// CPU switches schedule the new CPU's tick event for the /// same cycle (after unscheduling the old CPU's tick event). /// The switch needs to come before any tick events to make /// sure we don't tick both CPUs in the same cycle. - CPU_Switch_Pri = -31, + CPU_Switch_Pri = -31, /// For some reason "delayed" inter-cluster writebacks are /// scheduled before regular writebacks (which have default /// priority). Steve? - Delayed_Writeback_Pri = -1, + Delayed_Writeback_Pri = -1, /// Default is zero for historical reasons. - Default_Pri = 0, + Default_Pri = 0, /// Serailization needs to occur before tick events also, so /// that a serialize/unserialize is identical to an on-line /// CPU switch. - Serialize_Pri = 32, + Serialize_Pri = 32, /// CPU ticks must come after other associated CPU events /// (such as writebacks). - CPU_Tick_Pri = 50, + CPU_Tick_Pri = 50, /// Statistics events (dump, reset, etc.) come after /// everything else, but before exit. - Stat_Event_Pri = 90, + Stat_Event_Pri = 90, /// Progress events come at the end. Progress_Event_Pri = 95, /// If we want to exit on this cycle, it's the very last thing /// we do. - Sim_Exit_Pri = 100, + Sim_Exit_Pri = 100, /// Maximum priority - Maximum_Pri = SHRT_MAX + Maximum_Pri = SHRT_MAX }; /* @@ -181,7 +206,7 @@ class Event : public Serializable, public FastAlloc * @param queue that the event gets scheduled on */ Event(EventQueue *q, Priority p = Default_Pri) - : next(NULL), _queue(q), _priority(p), _flags(None) + : nextBin(NULL), nextInBin(NULL), _queue(q), _priority(p), _flags(None) { #ifndef NDEBUG instance = ++instanceCounter; @@ -343,9 +368,9 @@ class EventQueue : public Serializable virtual const std::string name() const { return objName; } // schedule the given event on this queue - void schedule(Event *ev); + void schedule(Event *ev, Tick when); void deschedule(Event *ev); - void reschedule(Event *ev); + void reschedule(Event *ev, Tick when); Tick nextTick() const { return head->when(); } Event *serviceOne(); @@ -379,6 +404,8 @@ class EventQueue : public Serializable Tick nextEventTime() { return empty() ? curTick : head->when(); } + bool debugVerify() const; + virtual void serialize(std::ostream &os); virtual void unserialize(Checkpoint *cp, const std::string §ion); }; @@ -396,53 +423,77 @@ class EventQueue : public Serializable // schedule at specified time (place on event queue specified via // constructor) inline void -Event::schedule(Tick t) +Event::schedule(Tick when) { - assert(!scheduled()); - assert(t >= curTick); - - setFlags(Scheduled); -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - _queue->schedule(this); + _queue->schedule(this, when); } inline void Event::deschedule() { - assert(scheduled()); - - clearFlags(Squashed); - clearFlags(Scheduled); _queue->deschedule(this); } inline void -Event::reschedule(Tick t, bool always) +Event::reschedule(Tick when, bool always) { - assert(scheduled() || always); - assert(t >= curTick); - -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - if (scheduled()) { - clearFlags(Squashed); - _queue->reschedule(this); + _queue->reschedule(this, when); } else { - setFlags(Scheduled); - _queue->schedule(this); + assert(always); + _queue->schedule(this, when); } } +inline bool +operator<(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() < r.priority()); +} + +inline bool +operator>(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() > r.priority()); +} + +inline bool +operator<=(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() <= r.priority()); +} +inline bool +operator>=(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() >= r.priority()); +} + +inline bool +operator==(const Event &l, const Event &r) +{ + return l.when() == r.when() && l.priority() == r.priority(); +} + +inline bool +operator!=(const Event &l, const Event &r) +{ + return l.when() != r.when() || l.priority() != r.priority(); +} + inline void -EventQueue::schedule(Event *event) +EventQueue::schedule(Event *event, Tick when) { + assert(when >= curTick); + assert(!event->scheduled()); + + event->setWhen(when); insert(event); + event->setFlags(Event::Scheduled); + if (DTRACE(Event)) event->trace("scheduled"); } @@ -450,19 +501,31 @@ EventQueue::schedule(Event *event) inline void EventQueue::deschedule(Event *event) { + assert(event->scheduled()); + remove(event); - if (DTRACE(Event)) - event->trace("descheduled"); + + event->clearFlags(Event::Squashed); + event->clearFlags(Event::Scheduled); if (event->getFlags(Event::AutoDelete)) delete event; + + if (DTRACE(Event)) + event->trace("descheduled"); } inline void -EventQueue::reschedule(Event *event) +EventQueue::reschedule(Event *event, Tick when) { + assert(when >= curTick); + assert(event->scheduled()); + remove(event); + event->setWhen(when); insert(event); + event->clearFlags(Event::Squashed); + if (DTRACE(Event)) event->trace("rescheduled"); }