#include <algorithm>
#include <cassert>
+#include <climits>
#include <map>
#include <string>
#include <vector>
#include "sim/serialize.hh"
#include "sim/host.hh"
-class EventQueue; // forward declaration
+class EventQueue; // forward declaration
//////////////////////
//
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
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,
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
/// 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
/// 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
};
/*
* @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;
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();
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);
};
// 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");
}
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");
}
projects / gem5.git / blobdiff