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/misc.hh"
  50 #include "base/trace.hh"
  51 #include "sim/serialize.hh"
  52
  53 class EventQueue;       // forward declaration
  54
  55 //////////////////////
  56 //
  57 // Main Event Queue
  58 //
  59 // Events on this queue are processed at the *beginning* of each
  60 // cycle, before the pipeline simulation is performed.
  61 //
  62 // defined in eventq.cc
  63 //
  64 //////////////////////
  65 extern EventQueue mainEventQueue;
  66
  67
  68 /*
  69  * An item on an event queue.  The action caused by a given
  70  * event is specified by deriving a subclass and overriding the
  71  * process() member function.
  72  */
  73 class Event : public Serializable, public FastAlloc
  74 {
  75     friend class EventQueue;
  76
  77   private:
  78
  79 #ifndef NDEBUG
  80     /// Global counter to generate unique IDs for Event instances
  81     static Counter instanceCounter;
  82
  83     /// This event's unique ID.  We can also use pointer values for
  84     /// this but they're not consistent across runs making debugging
  85     /// more difficult.  Thus we use a global counter value when
  86     /// debugging.
  87     Counter instanceId;
  88 #endif // NDEBUG
  89
  90     /// queue to which this event belongs (though it may or may not be
  91     /// scheduled on this queue yet)
  92     EventQueue *queue;
  93
  94     Event *next;
  95
  96     Tick _when; //!< timestamp when event should be processed
  97     int _priority;      //!< event priority
  98     char _flags;
  99
 100   protected:
 101     enum Flags {
 102         None = 0x0,
 103         Squashed = 0x1,
 104         Scheduled = 0x2,
 105         AutoDelete = 0x4,
 106         AutoSerialize = 0x8,
 107         IsExitEvent = 0x10
 108     };
 109
 110     bool getFlags(Flags f) const { return (_flags & f) == f; }
 111     void setFlags(Flags f) { _flags |= f; }
 112     void clearFlags(Flags f) { _flags &= ~f; }
 113
 114   protected:
 115     EventQueue *theQueue() const { return queue; }
 116
 117 #if TRACING_ON
 118     Tick when_created;  //!< Keep track of creation time For debugging
 119     Tick when_scheduled;        //!< Keep track of creation time For debugging
 120
 121     virtual void trace(const char *action);     //!< trace event activity
 122 #else
 123     void trace(const char *) {}
 124 #endif
 125
 126     unsigned annotated_value;
 127
 128   public:
 129
 130     /// Event priorities, to provide tie-breakers for events scheduled
 131     /// at the same cycle.  Most events are scheduled at the default
 132     /// priority; these values are used to control events that need to
 133     /// be ordered within a cycle.
 134     enum Priority {
 135         /// If we enable tracing on a particular cycle, do that as the
 136         /// very first thing so we don't miss any of the events on
 137         /// that cycle (even if we enter the debugger).
 138         Trace_Enable_Pri        = -101,
 139
 140         /// Breakpoints should happen before anything else (except
 141         /// enabling trace output), so we don't miss any action when
 142         /// debugging.
 143         Debug_Break_Pri         = -100,
 144
 145         /// CPU switches schedule the new CPU's tick event for the
 146         /// same cycle (after unscheduling the old CPU's tick event).
 147         /// The switch needs to come before any tick events to make
 148         /// sure we don't tick both CPUs in the same cycle.
 149         CPU_Switch_Pri          =   -31,
 150
 151         /// For some reason "delayed" inter-cluster writebacks are
 152         /// scheduled before regular writebacks (which have default
 153         /// priority).  Steve?
 154         Delayed_Writeback_Pri   =   -1,
 155
 156         /// Default is zero for historical reasons.
 157         Default_Pri             =    0,
 158
 159         /// Serailization needs to occur before tick events also, so
 160         /// that a serialize/unserialize is identical to an on-line
 161         /// CPU switch.
 162         Serialize_Pri           =   32,
 163
 164         /// CPU ticks must come after other associated CPU events
 165         /// (such as writebacks).
 166         CPU_Tick_Pri            =   50,
 167
 168         /// Statistics events (dump, reset, etc.) come after
 169         /// everything else, but before exit.
 170         Stat_Event_Pri          =   90,
 171
 172         /// Progress events come at the end.
 173         Progress_Event_Pri      =   95,
 174
 175         /// If we want to exit on this cycle, it's the very last thing
 176         /// we do.
 177         Sim_Exit_Pri            =  100
 178     };
 179
 180     /*
 181      * Event constructor
 182      * @param queue that the event gets scheduled on
 183      */
 184     Event(EventQueue *q, Priority p = Default_Pri)
 185         : queue(q), next(NULL), _priority(p), _flags(None),
 186 #if TRACING_ON
 187           when_created(curTick), when_scheduled(0),
 188 #endif
 189           annotated_value(0)
 190     {
 191 #ifndef NDEBUG
 192         instanceId = ++instanceCounter;
 193 #endif
 194     }
 195
 196     ~Event() {}
 197
 198     virtual const std::string name() const {
 199 #ifndef NDEBUG
 200         return csprintf("Event_%d", instanceId);
 201 #else
 202         return csprintf("Event_%x", (uintptr_t)this);
 203 #endif
 204     }
 205
 206     /// Determine if the current event is scheduled
 207     bool scheduled() const { return getFlags(Scheduled); }
 208
 209     /// Schedule the event with the current priority or default priority
 210     void schedule(Tick t);
 211
 212     /// Reschedule the event with the current priority
 213     void reschedule(Tick t);
 214
 215     /// Remove the event from the current schedule
 216     void deschedule();
 217
 218     /// Return a C string describing the event.  This string should
 219     /// *not* be dynamically allocated; just a const char array
 220     /// describing the event class.
 221     virtual const char *description();
 222
 223     /// Dump the current event data
 224     void dump();
 225
 226     /*
 227      * This member function is invoked when the event is processed
 228      * (occurs).  There is no default implementation; each subclass
 229      * must provide its own implementation.  The event is not
 230      * automatically deleted after it is processed (to allow for
 231      * statically allocated event objects).
 232      *
 233      * If the AutoDestroy flag is set, the object is deleted once it
 234      * is processed.
 235      */
 236     virtual void process() = 0;
 237
 238     void annotate(unsigned value) { annotated_value = value; };
 239     unsigned annotation() { return annotated_value; }
 240
 241     /// Squash the current event
 242     void squash() { setFlags(Squashed); }
 243
 244     /// Check whether the event is squashed
 245     bool squashed() { return getFlags(Squashed); }
 246
 247     /// See if this is a SimExitEvent (without resorting to RTTI)
 248     bool isExitEvent() { return getFlags(IsExitEvent); }
 249
 250     /// Get the time that the event is scheduled
 251     Tick when() const { return _when; }
 252
 253     /// Get the event priority
 254     int priority() const { return _priority; }
 255
 256     struct priority_compare :
 257     public std::binary_function<Event *, Event *, bool>
 258     {
 259         bool operator()(const Event *l, const Event *r) const {
 260             return l->when() >= r->when() || l->priority() >= r->priority();
 261         }
 262     };
 263
 264     virtual void serialize(std::ostream &os);
 265     virtual void unserialize(Checkpoint *cp, const std::string &section);
 266 };
 267
 268 template <class T, void (T::* F)()>
 269 void
 270 DelayFunction(Tick when, T *object)
 271 {
 272     class DelayEvent : public Event
 273     {
 274       private:
 275         T *object;
 276
 277       public:
 278         DelayEvent(Tick when, T *o)
 279             : Event(&mainEventQueue), object(o)
 280             { setFlags(this->AutoDestroy); schedule(when); }
 281         void process() { (object->*F)(); }
 282         const char *description() { return "delay"; }
 283     };
 284
 285     new DelayEvent(when, object);
 286 }
 287
 288 template <class T, void (T::* F)()>
 289 class EventWrapper : public Event
 290 {
 291   private:
 292     T *object;
 293
 294   public:
 295     EventWrapper(T *obj, bool del = false, EventQueue *q = &mainEventQueue,
 296                  Priority p = Default_Pri)
 297         : Event(q, p), object(obj)
 298     {
 299         if (del)
 300             setFlags(AutoDelete);
 301     }
 302     void process() { (object->*F)(); }
 303 };
 304
 305 /*
 306  * Queue of events sorted in time order
 307  */
 308 class EventQueue : public Serializable
 309 {
 310   protected:
 311     std::string objName;
 312
 313   private:
 314     Event *head;
 315
 316     void insert(Event *event);
 317     void remove(Event *event);
 318
 319   public:
 320
 321     // constructor
 322     EventQueue(const std::string &n)
 323         : objName(n), head(NULL)
 324     {}
 325
 326     virtual const std::string name() const { return objName; }
 327
 328     // schedule the given event on this queue
 329     void schedule(Event *ev);
 330     void deschedule(Event *ev);
 331     void reschedule(Event *ev);
 332
 333     Tick nextTick() { return head->when(); }
 334     Event *serviceOne();
 335
 336     // process all events up to the given timestamp.  we inline a
 337     // quick test to see if there are any events to process; if so,
 338     // call the internal out-of-line version to process them all.
 339     void serviceEvents(Tick when) {
 340         while (!empty()) {
 341             if (nextTick() > when)
 342                 break;
 343
 344             /**
 345              * @todo this assert is a good bug catcher.  I need to
 346              * make it true again.
 347              */
 348             //assert(head->when() >= when && "event scheduled in the past");
 349             serviceOne();
 350         }
 351     }
 352
 353     // default: process all events up to 'now' (curTick)
 354     void serviceEvents() { serviceEvents(curTick); }
 355
 356     // return true if no events are queued
 357     bool empty() { return head == NULL; }
 358
 359     void dump();
 360
 361     Tick nextEventTime() { return empty() ? curTick : head->when(); }
 362
 363     virtual void serialize(std::ostream &os);
 364     virtual void unserialize(Checkpoint *cp, const std::string &section);
 365 };
 366
 367
 368 //////////////////////
 369 //
 370 // inline functions
 371 //
 372 // can't put these inside declaration due to circular dependence
 373 // between Event and EventQueue classes.
 374 //
 375 //////////////////////
 376
 377 // schedule at specified time (place on event queue specified via
 378 // constructor)
 379 inline void
 380 Event::schedule(Tick t)
 381 {
 382     assert(!scheduled());
 383 //    if (t < curTick)
 384 //        warn("t is less than curTick, ensure you don't want cycles");
 385
 386     setFlags(Scheduled);
 387 #if TRACING_ON
 388     when_scheduled = curTick;
 389 #endif
 390     _when = t;
 391     queue->schedule(this);
 392 }
 393
 394 inline void
 395 Event::deschedule()
 396 {
 397     assert(scheduled());
 398
 399     clearFlags(Squashed);
 400     clearFlags(Scheduled);
 401     queue->deschedule(this);
 402 }
 403
 404 inline void
 405 Event::reschedule(Tick t)
 406 {
 407     assert(scheduled());
 408     clearFlags(Squashed);
 409
 410 #if TRACING_ON
 411     when_scheduled = curTick;
 412 #endif
 413     _when = t;
 414     queue->reschedule(this);
 415 }
 416
 417 inline void
 418 EventQueue::schedule(Event *event)
 419 {
 420     insert(event);
 421     if (DTRACE(Event))
 422         event->trace("scheduled");
 423 }
 424
 425 inline void
 426 EventQueue::deschedule(Event *event)
 427 {
 428     remove(event);
 429     if (DTRACE(Event))
 430         event->trace("descheduled");
 431 }
 432
 433 inline void
 434 EventQueue::reschedule(Event *event)
 435 {
 436     remove(event);
 437     insert(event);
 438     if (DTRACE(Event))
 439         event->trace("rescheduled");
 440 }
 441
 442
 443
 444 #endif // __SIM_EVENTQ_HH__