sim/eventq.hh

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