diff options
Diffstat (limited to 'src/sim/eventq.hh')
| -rw-r--r-- | src/sim/eventq.hh | 510 |
1 files changed, 312 insertions, 198 deletions
diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh index a454e5d64..33bb34252 100644 --- a/src/sim/eventq.hh +++ b/src/sim/eventq.hh @@ -36,45 +36,70 @@ #ifndef __SIM_EVENTQ_HH__ #define __SIM_EVENTQ_HH__ -#include <assert.h> - #include <algorithm> +#include <cassert> +#include <climits> #include <map> #include <string> #include <vector> -#include "sim/host.hh" // for Tick - #include "base/fast_alloc.hh" +#include "base/flags.hh" #include "base/misc.hh" #include "base/trace.hh" #include "sim/serialize.hh" +#include "sim/host.hh" -class EventQueue; // forward declaration - -////////////////////// -// -// Main Event Queue -// -// Events on this queue are processed at the *beginning* of each -// cycle, before the pipeline simulation is performed. -// -// defined in eventq.cc -// -////////////////////// -extern EventQueue mainEventQueue; +class EventQueue; // forward declaration +extern EventQueue mainEventQueue; /* * An item on an event queue. The action caused by a given * event is specified by deriving a subclass and overriding the * process() member function. + * + * Caution, the order of members is chosen to maximize data packing. */ class Event : public Serializable, public FastAlloc { friend class EventQueue; + protected: + typedef short FlagsType; + typedef ::Flags<FlagsType> Flags; + + static const FlagsType PublicRead = 0x003f; + static const FlagsType PublicWrite = 0x001d; + static const FlagsType Squashed = 0x0001; + static const FlagsType Scheduled = 0x0002; + static const FlagsType AutoDelete = 0x0004; + static const FlagsType AutoSerialize = 0x0008; + static const FlagsType IsExitEvent = 0x0010; + static const FlagsType IsMainQueue = 0x0020; +#ifdef EVENTQ_DEBUG + static const FlagsType Initialized = 0xf000; +#endif + private: + // 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); + + Tick _when; //!< timestamp when event should be processed + short _priority; //!< event priority + Flags flags; #ifndef NDEBUG /// Global counter to generate unique IDs for Event instances @@ -84,54 +109,85 @@ class Event : public Serializable, public FastAlloc /// this but they're not consistent across runs making debugging /// more difficult. Thus we use a global counter value when /// debugging. - Counter instanceId; -#endif // NDEBUG + Counter instance; /// queue to which this event belongs (though it may or may not be /// scheduled on this queue yet) EventQueue *queue; +#endif - Event *next; +#ifdef EVENTQ_DEBUG + Tick whenCreated; //!< time created + Tick whenScheduled; //!< time scheduled +#endif - Tick _when; //!< timestamp when event should be processed - int _priority; //!< event priority - char _flags; + void + setWhen(Tick when, EventQueue *q) + { + _when = when; +#ifndef NDEBUG + queue = q; +#endif +#ifdef EVENTQ_DEBUG + whenScheduled = curTick; +#endif + } protected: - enum Flags { - None = 0x0, - Squashed = 0x1, - Scheduled = 0x2, - AutoDelete = 0x4, - AutoSerialize = 0x8, - IsExitEvent = 0x10 - }; + /// Accessor for flags. + Flags + getFlags() const + { + return flags & PublicRead; + } - bool getFlags(Flags f) const { return (_flags & f) == f; } - void setFlags(Flags f) { _flags |= f; } - void clearFlags(Flags f) { _flags &= ~f; } + Flags + getFlags(Flags _flags) const + { + assert(flags.noneSet(~PublicRead)); + return flags.isSet(_flags); + } - protected: - EventQueue *theQueue() const { return queue; } + Flags + allFlags(Flags _flags) const + { + assert(_flags.noneSet(~PublicRead)); + return flags.allSet(_flags); + } -#if TRACING_ON - Tick when_created; //!< Keep track of creation time For debugging - Tick when_scheduled; //!< Keep track of creation time For debugging + /// Accessor for flags. + void + setFlags(Flags _flags) + { + assert(_flags.noneSet(~PublicWrite)); + flags.set(_flags); + } - virtual void trace(const char *action); //!< trace event activity -#else - void trace(const char *) {} -#endif + void + clearFlags(Flags _flags) + { + assert(_flags.noneSet(~PublicWrite)); + flags.clear(_flags); + } - unsigned annotated_value; + void + clearFlags() + { + flags.clear(PublicWrite); + } - public: + // This function isn't really useful if TRACING_ON is not defined + virtual void trace(const char *action); //!< trace event activity + public: /// Event priorities, to provide tie-breakers for events scheduled /// at the same cycle. Most events are scheduled at the default /// priority; these values are used to control events that need to /// be ordered within a cycle. enum Priority { + /// Minimum priority + 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 /// that cycle (even if we enter the debugger). @@ -140,81 +196,66 @@ 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 }; /* * Event constructor * @param queue that the event gets scheduled on */ - Event(EventQueue *q, Priority p = Default_Pri) - : queue(q), next(NULL), _priority(p), _flags(None), -#if TRACING_ON - when_created(curTick), when_scheduled(0), -#endif - annotated_value(0) + Event(Priority p = Default_Pri) + : nextBin(NULL), nextInBin(NULL), _priority(p) { #ifndef NDEBUG - instanceId = ++instanceCounter; + instance = ++instanceCounter; + queue = NULL; #endif - } - - ~Event() {} - - virtual const std::string name() const { -#ifndef NDEBUG - return csprintf("Event_%d", instanceId); -#else - return csprintf("Event_%x", (uintptr_t)this); +#ifdef EVENTQ_DEBUG + flags.set(Initialized); + whenCreated = curTick; + whenScheduled = 0; #endif } - /// Determine if the current event is scheduled - bool scheduled() const { return getFlags(Scheduled); } - - /// Schedule the event with the current priority or default priority - void schedule(Tick t); - - /// Reschedule the event with the current priority - // always parameter means to schedule if not already scheduled - void reschedule(Tick t, bool always = false); - - /// Remove the event from the current schedule - void deschedule(); + virtual ~Event(); + virtual const std::string name() const; /// Return a C string describing the event. This string should /// *not* be dynamically allocated; just a const char array @@ -222,8 +263,9 @@ class Event : public Serializable, public FastAlloc virtual const char *description() const; /// Dump the current event data - void dump(); + void dump() const; + public: /* * This member function is invoked when the event is processed * (occurs). There is no default implementation; each subclass @@ -236,17 +278,17 @@ class Event : public Serializable, public FastAlloc */ virtual void process() = 0; - void annotate(unsigned value) { annotated_value = value; }; - unsigned annotation() { return annotated_value; } + /// Determine if the current event is scheduled + bool scheduled() const { return flags.isSet(Scheduled); } /// Squash the current event - void squash() { setFlags(Squashed); } + void squash() { flags.set(Squashed); } /// Check whether the event is squashed - bool squashed() { return getFlags(Squashed); } + bool squashed() const { return flags.isSet(Squashed); } /// See if this is a SimExitEvent (without resorting to RTTI) - bool isExitEvent() { return getFlags(IsExitEvent); } + bool isExitEvent() const { return flags.isSet(IsExitEvent); } /// Get the time that the event is scheduled Tick when() const { return _when; } @@ -254,65 +296,20 @@ class Event : public Serializable, public FastAlloc /// Get the event priority int priority() const { return _priority; } - struct priority_compare : - public std::binary_function<Event *, Event *, bool> +#ifndef SWIG + struct priority_compare + : public std::binary_function<Event *, Event *, bool> { - bool operator()(const Event *l, const Event *r) const { + bool + operator()(const Event *l, const Event *r) const + { return l->when() >= r->when() || l->priority() >= r->priority(); } }; virtual void serialize(std::ostream &os); virtual void unserialize(Checkpoint *cp, const std::string §ion); -}; - -template <class T, void (T::* F)()> -void -DelayFunction(Tick when, T *object) -{ - class DelayEvent : public Event - { - private: - T *object; - - public: - DelayEvent(Tick when, T *o) - : Event(&mainEventQueue), object(o) - { setFlags(this->AutoDestroy); schedule(when); } - void process() { (object->*F)(); } - const char *description() const { return "delay"; } - }; - - new DelayEvent(when, object); -} - -template <class T, void (T::* F)()> -class EventWrapper : public Event -{ - private: - T *object; - - public: - EventWrapper(T *obj, bool del = false, - EventQueue *q = &mainEventQueue, - Priority p = Default_Pri) - : Event(q, p), object(obj) - { - if (del) - setFlags(AutoDelete); - } - - EventWrapper(T *obj, Tick t, bool del = false, - EventQueue *q = &mainEventQueue, - Priority p = Default_Pri) - : Event(q, p), object(obj) - { - if (del) - setFlags(AutoDelete); - schedule(t); - } - - void process() { (object->*F)(); } +#endif }; /* @@ -320,18 +317,14 @@ class EventWrapper : public Event */ class EventQueue : public Serializable { - protected: - std::string objName; - private: + std::string objName; Event *head; void insert(Event *event); void remove(Event *event); public: - - // constructor EventQueue(const std::string &n) : objName(n), head(NULL) {} @@ -339,17 +332,19 @@ class EventQueue : public Serializable virtual const std::string name() const { return objName; } // schedule the given event on this queue - void schedule(Event *ev); - void deschedule(Event *ev); - void reschedule(Event *ev); + void schedule(Event *event, Tick when); + void deschedule(Event *event); + void reschedule(Event *event, Tick when, bool always = false); - Tick nextTick() { return head->when(); } + Tick nextTick() const { return head->when(); } Event *serviceOne(); // process all events up to the given timestamp. we inline a // quick test to see if there are any events to process; if so, // call the internal out-of-line version to process them all. - void serviceEvents(Tick when) { + void + serviceEvents(Tick when) + { while (!empty()) { if (nextTick() > when) break; @@ -367,76 +362,129 @@ class EventQueue : public Serializable void serviceEvents() { serviceEvents(curTick); } // return true if no events are queued - bool empty() { return head == NULL; } + bool empty() const { return head == NULL; } - void dump(); + void dump() const; Tick nextEventTime() { return empty() ? curTick : head->when(); } + bool debugVerify() const; + +#ifndef SWIG virtual void serialize(std::ostream &os); virtual void unserialize(Checkpoint *cp, const std::string §ion); +#endif }; +#ifndef SWIG +class EventManager +{ + protected: + /** A pointer to this object's event queue */ + EventQueue *eventq; -////////////////////// -// -// inline functions -// -// can't put these inside declaration due to circular dependence -// between Event and EventQueue classes. -// -////////////////////// + public: + EventManager(EventManager &em) : eventq(em.queue()) {} + EventManager(EventManager *em) : eventq(em ? em->queue() : NULL) {} + EventManager(EventQueue *eq) : eventq(eq) {} -// schedule at specified time (place on event queue specified via -// constructor) -inline void -Event::schedule(Tick t) -{ - assert(!scheduled()); -// if (t < curTick) -// warn("t is less than curTick, ensure you don't want cycles"); + EventQueue * + queue() const + { + return eventq; + } - setFlags(Scheduled); -#if TRACING_ON - when_scheduled = curTick; -#endif - _when = t; - queue->schedule(this); -} + void + schedule(Event &event, Tick when) + { + eventq->schedule(&event, when); + } -inline void -Event::deschedule() + void + deschedule(Event &event) + { + eventq->deschedule(&event); + } + + void + reschedule(Event &event, Tick when, bool always = false) + { + eventq->reschedule(&event, when, always); + } + + void + schedule(Event *event, Tick when) + { + eventq->schedule(event, when); + } + + void + deschedule(Event *event) + { + eventq->deschedule(event); + } + + void + reschedule(Event *event, Tick when, bool always = false) + { + eventq->reschedule(event, when, always); + } +}; + +template <class T, void (T::* F)()> +void +DelayFunction(EventQueue *eventq, Tick when, T *object) { - assert(scheduled()); + class DelayEvent : public Event + { + private: + T *object; + + public: + DelayEvent(T *o) + : object(o) + { this->setFlags(AutoDelete); } + void process() { (object->*F)(); } + const char *description() const { return "delay"; } + }; - clearFlags(Squashed); - clearFlags(Scheduled); - queue->deschedule(this); + eventq->schedule(new DelayEvent(object), when); } -inline void -Event::reschedule(Tick t, bool always) +template <class T, void (T::* F)()> +class EventWrapper : public Event { - assert(scheduled() || always); + private: + T *object; -#if TRACING_ON - when_scheduled = curTick; -#endif - _when = t; - - if (scheduled()) { - clearFlags(Squashed); - queue->reschedule(this); - } else { - setFlags(Scheduled); - queue->schedule(this); + public: + EventWrapper(T *obj, bool del = false, Priority p = Default_Pri) + : Event(p), object(obj) + { + if (del) + setFlags(AutoDelete); } -} + + void process() { (object->*F)(); } +}; inline void -EventQueue::schedule(Event *event) +EventQueue::schedule(Event *event, Tick when) { + assert(when >= curTick); + assert(!event->scheduled()); +#ifdef EVENTQ_DEBUG + assert((event->flags & Event::Initialized) == Event::Initialized); +#endif + + event->setWhen(when, this); insert(event); + event->flags.set(Event::Scheduled); + if (this == &mainEventQueue) + event->flags.set(Event::IsMainQueue); + else + event->flags.clear(Event::IsMainQueue); + if (DTRACE(Event)) event->trace("scheduled"); } @@ -444,20 +492,86 @@ EventQueue::schedule(Event *event) inline void EventQueue::deschedule(Event *event) { + assert(event->scheduled()); +#ifdef EVENTQ_DEBUG + assert((event->flags & Event::Initialized) == Event::Initialized); +#endif + remove(event); + + event->flags.clear(Event::Squashed); + event->flags.clear(Event::Scheduled); + + if (event->flags.isSet(Event::AutoDelete)) + delete event; + if (DTRACE(Event)) event->trace("descheduled"); } inline void -EventQueue::reschedule(Event *event) +EventQueue::reschedule(Event *event, Tick when, bool always) { - remove(event); + assert(when >= curTick); + assert(always || event->scheduled()); +#ifdef EVENTQ_DEBUG + assert((event->flags & Event::Initialized) == Event::Initialized); +#endif + + if (event->scheduled()) + remove(event); + + event->setWhen(when, this); insert(event); + event->flags.clear(Event::Squashed); + event->flags.set(Event::Scheduled); + if (this == &mainEventQueue) + event->flags.set(Event::IsMainQueue); + else + event->flags.clear(Event::IsMainQueue); + if (DTRACE(Event)) event->trace("rescheduled"); } +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(); +} +#endif #endif // __SIM_EVENTQ_HH__ |