src/sim/eventq.hh

   1 /*
   2  * Copyright (c) 2000-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Steve Reinhardt
  29  *          Nathan Binkert
  30  */
  31
  32 /* @file
  33  * EventQueue interfaces
  34  */
  35
  36 #ifndef __SIM_EVENTQ_HH__
  37 #define __SIM_EVENTQ_HH__
  38
  39 #include <assert.h>
  40
  41 #include <algorithm>
  42 #include <map>
  43 #include <string>
  44 #include <vector>
  45
  46 #include "sim/host.hh"  // for Tick
  47
  48 #include "base/fast_alloc.hh"
  49 #include "base/trace.hh"
  50 #include "sim/serialize.hh"
  51
  52 class EventQueue;       // forward declaration
  53
  54 //////////////////////
  55 //
  56 // Main Event Queue
  57 //
  58 // Events on this queue are processed at the *beginning* of each
  59 // cycle, before the pipeline simulation is performed.
  60 //
  61 // defined in eventq.cc
  62 //
  63 //////////////////////
  64 extern EventQueue mainEventQueue;
  65
  66
  67 /*
  68  * An item on an event queue.  The action caused by a given
  69  * event is specified by deriving a subclass and overriding the
  70  * process() member function.
  71  */
  72 class Event : public Serializable, public FastAlloc
  73 {
  74     friend class EventQueue;
  75
  76   private:
  77     /// queue to which this event belongs (though it may or may not be
  78     /// scheduled on this queue yet)
  79     EventQueue *queue;
  80
  81     Event *next;
  82
  83     Tick _when; //!< timestamp when event should be processed
  84     int _priority;      //!< event priority
  85     char _flags;
  86
  87   protected:
  88     enum Flags {
  89         None = 0x0,
  90         Squashed = 0x1,
  91         Scheduled = 0x2,
  92         AutoDelete = 0x4,
  93         AutoSerialize = 0x8,
  94         IsExitEvent = 0x10
  95     };
  96
  97     bool getFlags(Flags f) const { return (_flags & f) == f; }
  98     void setFlags(Flags f) { _flags |= f; }
  99     void clearFlags(Flags f) { _flags &= ~f; }
 100
 101   protected:
 102     EventQueue *theQueue() const { return queue; }
 103
 104 #if TRACING_ON
 105     Tick when_created;  //!< Keep track of creation time For debugging
 106     Tick when_scheduled;        //!< Keep track of creation time For debugging
 107
 108     virtual void trace(const char *action);     //!< trace event activity
 109 #else
 110     void trace(const char *) {}
 111 #endif
 112
 113     unsigned annotated_value;
 114
 115   public:
 116
 117     /// Event priorities, to provide tie-breakers for events scheduled
 118     /// at the same cycle.  Most events are scheduled at the default
 119     /// priority; these values are used to control events that need to
 120     /// be ordered within a cycle.
 121     enum Priority {
 122         /// Breakpoints should happen before anything else, so we
 123         /// don't miss any action when debugging.
 124         Debug_Break_Pri         = -100,
 125
 126         /// For some reason "delayed" inter-cluster writebacks are
 127         /// scheduled before regular writebacks (which have default
 128         /// priority).  Steve?
 129         Delayed_Writeback_Pri   =   -1,
 130
 131         /// Default is zero for historical reasons.
 132         Default_Pri             =    0,
 133
 134         /// CPU switches schedule the new CPU's tick event for the
 135         /// same cycle (after unscheduling the old CPU's tick event).
 136         /// The switch needs to come before any tick events to make
 137         /// sure we don't tick both CPUs in the same cycle.
 138         CPU_Switch_Pri          =   31,
 139
 140         /// Serailization needs to occur before tick events also, so
 141         /// that a serialize/unserialize is identical to an on-line
 142         /// CPU switch.
 143         Serialize_Pri           =   32,
 144
 145         /// CPU ticks must come after other associated CPU events
 146         /// (such as writebacks).
 147         CPU_Tick_Pri            =   50,
 148
 149         /// Statistics events (dump, reset, etc.) come after
 150         /// everything else, but before exit.
 151         Stat_Event_Pri          =   90,
 152
 153         /// If we want to exit on this cycle, it's the very last thing
 154         /// we do.
 155         Sim_Exit_Pri            =  100
 156     };
 157
 158     /*
 159      * Event constructor
 160      * @param queue that the event gets scheduled on
 161      */
 162     Event(EventQueue *q, Priority p = Default_Pri)
 163         : queue(q), next(NULL), _priority(p), _flags(None),
 164 #if TRACING_ON
 165           when_created(curTick), when_scheduled(0),
 166 #endif
 167           annotated_value(0)
 168     {
 169     }
 170
 171     ~Event() {}
 172
 173     virtual const std::string name() const {
 174         return csprintf("Event_%x", (uintptr_t)this);
 175     }
 176
 177     /// Determine if the current event is scheduled
 178     bool scheduled() const { return getFlags(Scheduled); }
 179
 180     /// Schedule the event with the current priority or default priority
 181     void schedule(Tick t);
 182
 183     /// Reschedule the event with the current priority
 184     void reschedule(Tick t);
 185
 186     /// Remove the event from the current schedule
 187     void deschedule();
 188
 189     /// Return a C string describing the event.  This string should
 190     /// *not* be dynamically allocated; just a const char array
 191     /// describing the event class.
 192     virtual const char *description();
 193
 194     /// Dump the current event data
 195     void dump();
 196
 197     /*
 198      * This member function is invoked when the event is processed
 199      * (occurs).  There is no default implementation; each subclass
 200      * must provide its own implementation.  The event is not
 201      * automatically deleted after it is processed (to allow for
 202      * statically allocated event objects).
 203      *
 204      * If the AutoDestroy flag is set, the object is deleted once it
 205      * is processed.
 206      */
 207     virtual void process() = 0;
 208
 209     void annotate(unsigned value) { annotated_value = value; };
 210     unsigned annotation() { return annotated_value; }
 211
 212     /// Squash the current event
 213     void squash() { setFlags(Squashed); }
 214
 215     /// Check whether the event is squashed
 216     bool squashed() { return getFlags(Squashed); }
 217
 218     /// See if this is a SimExitEvent (without resorting to RTTI)
 219     bool isExitEvent() { return getFlags(IsExitEvent); }
 220
 221     /// Get the time that the event is scheduled
 222     Tick when() const { return _when; }
 223
 224     /// Get the event priority
 225     int priority() const { return _priority; }
 226
 227     struct priority_compare :
 228     public std::binary_function<Event *, Event *, bool>
 229     {
 230         bool operator()(const Event *l, const Event *r) const {
 231             return l->when() >= r->when() || l->priority() >= r->priority();
 232         }
 233     };
 234
 235     virtual void serialize(std::ostream &os);
 236     virtual void unserialize(Checkpoint *cp, const std::string &section);
 237 };
 238
 239 template <class T, void (T::* F)()>
 240 void
 241 DelayFunction(Tick when, T *object)
 242 {
 243     class DelayEvent : public Event
 244     {
 245       private:
 246         T *object;
 247
 248       public:
 249         DelayEvent(Tick when, T *o)
 250             : Event(&mainEventQueue), object(o)
 251             { setFlags(this->AutoDestroy); schedule(when); }
 252         void process() { (object->*F)(); }
 253         const char *description() { return "delay"; }
 254     };
 255
 256     new DelayEvent(when, object);
 257 }
 258
 259 template <class T, void (T::* F)()>
 260 class EventWrapper : public Event
 261 {
 262   private:
 263     T *object;
 264
 265   public:
 266     EventWrapper(T *obj, bool del = false, EventQueue *q = &mainEventQueue,
 267                  Priority p = Default_Pri)
 268         : Event(q, p), object(obj)
 269     {
 270         if (del)
 271             setFlags(AutoDelete);
 272     }
 273     void process() { (object->*F)(); }
 274 };
 275
 276 /*
 277  * Queue of events sorted in time order
 278  */
 279 class EventQueue : public Serializable
 280 {
 281   protected:
 282     std::string objName;
 283
 284   private:
 285     Event *head;
 286
 287     void insert(Event *event);
 288     void remove(Event *event);
 289
 290   public:
 291
 292     // constructor
 293     EventQueue(const std::string &n)
 294         : objName(n), head(NULL)
 295     {}
 296
 297     virtual const std::string name() const { return objName; }
 298
 299     // schedule the given event on this queue
 300     void schedule(Event *ev);
 301     void deschedule(Event *ev);
 302     void reschedule(Event *ev);
 303
 304     Tick nextTick() { return head->when(); }
 305     Event *serviceOne();
 306
 307     // process all events up to the given timestamp.  we inline a
 308     // quick test to see if there are any events to process; if so,
 309     // call the internal out-of-line version to process them all.
 310     void serviceEvents(Tick when) {
 311         while (!empty()) {
 312             if (nextTick() > when)
 313                 break;
 314
 315             /**
 316              * @todo this assert is a good bug catcher.  I need to
 317              * make it true again.
 318              */
 319             //assert(head->when() >= when && "event scheduled in the past");
 320             serviceOne();
 321         }
 322     }
 323
 324     // default: process all events up to 'now' (curTick)
 325     void serviceEvents() { serviceEvents(curTick); }
 326
 327     // return true if no events are queued
 328     bool empty() { return head == NULL; }
 329
 330     void dump();
 331
 332     Tick nextEventTime() { return empty() ? curTick : head->when(); }
 333
 334     virtual void serialize(std::ostream &os);
 335     virtual void unserialize(Checkpoint *cp, const std::string &section);
 336 };
 337
 338
 339 //////////////////////
 340 //
 341 // inline functions
 342 //
 343 // can't put these inside declaration due to circular dependence
 344 // between Event and EventQueue classes.
 345 //
 346 //////////////////////
 347
 348 // schedule at specified time (place on event queue specified via
 349 // constructor)
 350 inline void
 351 Event::schedule(Tick t)
 352 {
 353     assert(!scheduled());
 354     assert(t >= curTick);
 355
 356     setFlags(Scheduled);
 357 #if TRACING_ON
 358     when_scheduled = curTick;
 359 #endif
 360     _when = t;
 361     queue->schedule(this);
 362 }
 363
 364 inline void
 365 Event::deschedule()
 366 {
 367     assert(scheduled());
 368
 369     clearFlags(Squashed);
 370     clearFlags(Scheduled);
 371     queue->deschedule(this);
 372 }
 373
 374 inline void
 375 Event::reschedule(Tick t)
 376 {
 377     assert(scheduled());
 378     clearFlags(Squashed);
 379
 380 #if TRACING_ON
 381     when_scheduled = curTick;
 382 #endif
 383     _when = t;
 384     queue->reschedule(this);
 385 }
 386
 387 inline void
 388 EventQueue::schedule(Event *event)
 389 {
 390     insert(event);
 391     if (DTRACE(Event))
 392         event->trace("scheduled");
 393 }
 394
 395 inline void
 396 EventQueue::deschedule(Event *event)
 397 {
 398     remove(event);
 399     if (DTRACE(Event))
 400         event->trace("descheduled");
 401 }
 402
 403 inline void
 404 EventQueue::reschedule(Event *event)
 405 {
 406     remove(event);
 407     insert(event);
 408     if (DTRACE(Event))
 409         event->trace("rescheduled");
 410 }
 411
 412
 413
 414 #endif // __SIM_EVENTQ_HH__