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 <algorithm>
  40 #include <cassert>
  41 #include <climits>
  42 #include <map>
  43 #include <string>
  44 #include <vector>
  45
  46 #include "base/fast_alloc.hh"
  47 #include "base/misc.hh"
  48 #include "base/trace.hh"
  49 #include "sim/serialize.hh"
  50 #include "sim/host.hh"
  51
  52 class EventQueue;       // forward declaration
  53
  54 extern EventQueue mainEventQueue;
  55
  56 /*
  57  * An item on an event queue.  The action caused by a given
  58  * event is specified by deriving a subclass and overriding the
  59  * process() member function.
  60  *
  61  * Caution, the order of members is chosen to maximize data packing.
  62  */
  63 class Event : public Serializable, public FastAlloc
  64 {
  65     friend class EventQueue;
  66
  67   private:
  68     // The event queue is now a linked list of linked lists.  The
  69     // 'nextBin' pointer is to find the bin, where a bin is defined as
  70     // when+priority.  All events in the same bin will be stored in a
  71     // second linked list (a stack) maintained by the 'nextInBin'
  72     // pointer.  The list will be accessed in LIFO order.  The end
  73     // result is that the insert/removal in 'nextBin' is
  74     // linear/constant, and the lookup/removal in 'nextInBin' is
  75     // constant/constant.  Hopefully this is a significant improvement
  76     // over the current fully linear insertion.
  77     Event *nextBin;
  78     Event *nextInBin;
  79
  80     static Event *insertBefore(Event *event, Event *curr);
  81     static Event *removeItem(Event *event, Event *last);
  82
  83     Tick _when;         //!< timestamp when event should be processed
  84     short _priority;    //!< event priority
  85     short _flags;
  86
  87 #ifndef NDEBUG
  88     /// Global counter to generate unique IDs for Event instances
  89     static Counter instanceCounter;
  90
  91     /// This event's unique ID.  We can also use pointer values for
  92     /// this but they're not consistent across runs making debugging
  93     /// more difficult.  Thus we use a global counter value when
  94     /// debugging.
  95     Counter instance;
  96
  97     /// queue to which this event belongs (though it may or may not be
  98     /// scheduled on this queue yet)
  99     EventQueue *queue;
 100 #endif
 101
 102 #ifdef EVENTQ_DEBUG
 103     Tick whenCreated;   //!< time created
 104     Tick whenScheduled; //!< time scheduled
 105 #endif
 106
 107     void
 108     setWhen(Tick when, EventQueue *q)
 109     {
 110         _when = when;
 111 #ifndef NDEBUG
 112         queue = q;
 113 #endif
 114 #ifdef EVENTQ_DEBUG
 115         whenScheduled = curTick;
 116 #endif
 117     }
 118
 119   protected:
 120     enum Flags {
 121         None = 0x0,
 122         Squashed = 0x1,
 123         Scheduled = 0x2,
 124         AutoDelete = 0x4,
 125         AutoSerialize = 0x8,
 126         IsExitEvent = 0x10,
 127         IsMainQueue = 0x20
 128     };
 129
 130     bool getFlags(Flags f) const { return (_flags & f) == f; }
 131     void setFlags(Flags f) { _flags |= f; }
 132     void clearFlags(Flags f) { _flags &= ~f; }
 133
 134   protected:
 135     // This function isn't really useful if TRACING_ON is not defined
 136     virtual void trace(const char *action);     //!< trace event activity
 137
 138   public:
 139     /// Event priorities, to provide tie-breakers for events scheduled
 140     /// at the same cycle.  Most events are scheduled at the default
 141     /// priority; these values are used to control events that need to
 142     /// be ordered within a cycle.
 143     enum Priority {
 144         /// Minimum priority
 145         Minimum_Pri             = SHRT_MIN,
 146
 147         /// If we enable tracing on a particular cycle, do that as the
 148         /// very first thing so we don't miss any of the events on
 149         /// that cycle (even if we enter the debugger).
 150         Trace_Enable_Pri        = -101,
 151
 152         /// Breakpoints should happen before anything else (except
 153         /// enabling trace output), so we don't miss any action when
 154         /// debugging.
 155         Debug_Break_Pri         = -100,
 156
 157         /// CPU switches schedule the new CPU's tick event for the
 158         /// same cycle (after unscheduling the old CPU's tick event).
 159         /// The switch needs to come before any tick events to make
 160         /// sure we don't tick both CPUs in the same cycle.
 161         CPU_Switch_Pri          =   -31,
 162
 163         /// For some reason "delayed" inter-cluster writebacks are
 164         /// scheduled before regular writebacks (which have default
 165         /// priority).  Steve?
 166         Delayed_Writeback_Pri   =   -1,
 167
 168         /// Default is zero for historical reasons.
 169         Default_Pri             =    0,
 170
 171         /// Serailization needs to occur before tick events also, so
 172         /// that a serialize/unserialize is identical to an on-line
 173         /// CPU switch.
 174         Serialize_Pri           =   32,
 175
 176         /// CPU ticks must come after other associated CPU events
 177         /// (such as writebacks).
 178         CPU_Tick_Pri            =   50,
 179
 180         /// Statistics events (dump, reset, etc.) come after
 181         /// everything else, but before exit.
 182         Stat_Event_Pri          =   90,
 183
 184         /// Progress events come at the end.
 185         Progress_Event_Pri      =   95,
 186
 187         /// If we want to exit on this cycle, it's the very last thing
 188         /// we do.
 189         Sim_Exit_Pri            =  100,
 190
 191         /// Maximum priority
 192         Maximum_Pri             = SHRT_MAX
 193     };
 194
 195     /*
 196      * Event constructor
 197      * @param queue that the event gets scheduled on
 198      */
 199     Event(Priority p = Default_Pri)
 200         : nextBin(NULL), nextInBin(NULL), _priority(p), _flags(None)
 201     {
 202 #ifndef NDEBUG
 203         instance = ++instanceCounter;
 204         queue = NULL;
 205 #endif
 206 #ifdef EVENTQ_DEBUG
 207         whenCreated = curTick;
 208         whenScheduled = 0;
 209 #endif
 210     }
 211
 212     virtual
 213     ~Event()
 214     {
 215     }
 216
 217     virtual const std::string
 218     name() const
 219     {
 220 #ifndef NDEBUG
 221         return csprintf("Event_%d", instance);
 222 #else
 223         return csprintf("Event_%x", (uintptr_t)this);
 224 #endif
 225     }
 226
 227     /// Return a C string describing the event.  This string should
 228     /// *not* be dynamically allocated; just a const char array
 229     /// describing the event class.
 230     virtual const char *description() const;
 231
 232     /// Dump the current event data
 233     void dump() const;
 234
 235   public:
 236     /*
 237      * This member function is invoked when the event is processed
 238      * (occurs).  There is no default implementation; each subclass
 239      * must provide its own implementation.  The event is not
 240      * automatically deleted after it is processed (to allow for
 241      * statically allocated event objects).
 242      *
 243      * If the AutoDestroy flag is set, the object is deleted once it
 244      * is processed.
 245      */
 246     virtual void process() = 0;
 247
 248     /// Determine if the current event is scheduled
 249     bool scheduled() const { return getFlags(Scheduled); }
 250
 251     /// Squash the current event
 252     void squash() { setFlags(Squashed); }
 253
 254     /// Check whether the event is squashed
 255     bool squashed() const { return getFlags(Squashed); }
 256
 257     /// See if this is a SimExitEvent (without resorting to RTTI)
 258     bool isExitEvent() const { return getFlags(IsExitEvent); }
 259
 260     /// Get the time that the event is scheduled
 261     Tick when() const { return _when; }
 262
 263     /// Get the event priority
 264     int priority() const { return _priority; }
 265
 266 #ifndef SWIG
 267     struct priority_compare
 268         : public std::binary_function<Event *, Event *, bool>
 269     {
 270         bool
 271         operator()(const Event *l, const Event *r) const
 272         {
 273             return l->when() >= r->when() || l->priority() >= r->priority();
 274         }
 275     };
 276
 277     virtual void serialize(std::ostream &os);
 278     virtual void unserialize(Checkpoint *cp, const std::string &section);
 279 #endif
 280 };
 281
 282 /*
 283  * Queue of events sorted in time order
 284  */
 285 class EventQueue : public Serializable
 286 {
 287   private:
 288     std::string objName;
 289     Event *head;
 290
 291     void insert(Event *event);
 292     void remove(Event *event);
 293
 294   public:
 295     EventQueue(const std::string &n)
 296         : objName(n), head(NULL)
 297     {}
 298
 299     virtual const std::string name() const { return objName; }
 300
 301     // schedule the given event on this queue
 302     void schedule(Event *event, Tick when);
 303     void deschedule(Event *event);
 304     void reschedule(Event *event, Tick when, bool always = false);
 305
 306     Tick nextTick() const { return head->when(); }
 307     Event *serviceOne();
 308
 309     // process all events up to the given timestamp.  we inline a
 310     // quick test to see if there are any events to process; if so,
 311     // call the internal out-of-line version to process them all.
 312     void
 313     serviceEvents(Tick when)
 314     {
 315         while (!empty()) {
 316             if (nextTick() > when)
 317                 break;
 318
 319             /**
 320              * @todo this assert is a good bug catcher.  I need to
 321              * make it true again.
 322              */
 323             //assert(head->when() >= when && "event scheduled in the past");
 324             serviceOne();
 325         }
 326     }
 327
 328     // default: process all events up to 'now' (curTick)
 329     void serviceEvents() { serviceEvents(curTick); }
 330
 331     // return true if no events are queued
 332     bool empty() const { return head == NULL; }
 333
 334     void dump() const;
 335
 336     Tick nextEventTime() { return empty() ? curTick : head->when(); }
 337
 338     bool debugVerify() const;
 339
 340 #ifndef SWIG
 341     virtual void serialize(std::ostream &os);
 342     virtual void unserialize(Checkpoint *cp, const std::string &section);
 343 #endif
 344 };
 345
 346 #ifndef SWIG
 347 class EventManager
 348 {
 349   protected:
 350     /** A pointer to this object's event queue */
 351     EventQueue *eventq;
 352
 353   public:
 354     EventManager(EventManager &em) : eventq(em.queue()) {}
 355     EventManager(EventManager *em) : eventq(em ? em->queue() : NULL) {}
 356     EventManager(EventQueue *eq) : eventq(eq) {}
 357
 358     EventQueue *
 359     queue() const
 360     {
 361         return eventq;
 362     }
 363
 364     void
 365     schedule(Event &event, Tick when)
 366     {
 367         eventq->schedule(&event, when);
 368     }
 369
 370     void
 371     deschedule(Event &event)
 372     {
 373         eventq->deschedule(&event);
 374     }
 375
 376     void
 377     reschedule(Event &event, Tick when, bool always = false)
 378     {
 379         eventq->reschedule(&event, when, always);
 380     }
 381
 382     void
 383     schedule(Event *event, Tick when)
 384     {
 385         eventq->schedule(event, when);
 386     }
 387
 388     void
 389     deschedule(Event *event)
 390     {
 391         eventq->deschedule(event);
 392     }
 393
 394     void
 395     reschedule(Event *event, Tick when, bool always = false)
 396     {
 397         eventq->reschedule(event, when, always);
 398     }
 399 };
 400
 401 template <class T, void (T::* F)()>
 402 void
 403 DelayFunction(EventQueue *eventq, Tick when, T *object)
 404 {
 405     class DelayEvent : public Event
 406     {
 407       private:
 408         T *object;
 409
 410       public:
 411         DelayEvent(T *o)
 412             : object(o)
 413         { setFlags(this->AutoDestroy); }
 414         void process() { (object->*F)(); }
 415         const char *description() const { return "delay"; }
 416     };
 417
 418     eventq->schedule(new DelayEvent(object), when);
 419 }
 420
 421 template <class T, void (T::* F)()>
 422 class EventWrapper : public Event
 423 {
 424   private:
 425     T *object;
 426
 427   public:
 428     EventWrapper(T *obj, bool del = false, Priority p = Default_Pri)
 429         : Event(p), object(obj)
 430     {
 431         if (del)
 432             setFlags(AutoDelete);
 433     }
 434
 435     void process() { (object->*F)(); }
 436 };
 437
 438 inline void
 439 EventQueue::schedule(Event *event, Tick when)
 440 {
 441     assert(when >= curTick);
 442     assert(!event->scheduled());
 443
 444     event->setWhen(when, this);
 445     insert(event);
 446     event->setFlags(Event::Scheduled);
 447     if (this == &mainEventQueue)
 448         event->setFlags(Event::IsMainQueue);
 449     else
 450         event->clearFlags(Event::IsMainQueue);
 451
 452     if (DTRACE(Event))
 453         event->trace("scheduled");
 454 }
 455
 456 inline void
 457 EventQueue::deschedule(Event *event)
 458 {
 459     assert(event->scheduled());
 460
 461     remove(event);
 462
 463     event->clearFlags(Event::Squashed);
 464     event->clearFlags(Event::Scheduled);
 465
 466     if (event->getFlags(Event::AutoDelete))
 467         delete event;
 468
 469     if (DTRACE(Event))
 470         event->trace("descheduled");
 471 }
 472
 473 inline void
 474 EventQueue::reschedule(Event *event, Tick when, bool always)
 475 {
 476     assert(when >= curTick);
 477     assert(always || event->scheduled());
 478
 479     if (event->scheduled())
 480         remove(event);
 481
 482     event->setWhen(when, this);
 483     insert(event);
 484     event->clearFlags(Event::Squashed);
 485     event->setFlags(Event::Scheduled);
 486     if (this == &mainEventQueue)
 487         event->setFlags(Event::IsMainQueue);
 488     else
 489         event->clearFlags(Event::IsMainQueue);
 490
 491     if (DTRACE(Event))
 492         event->trace("rescheduled");
 493 }
 494
 495 inline bool
 496 operator<(const Event &l, const Event &r)
 497 {
 498     return l.when() < r.when() ||
 499         (l.when() == r.when() && l.priority() < r.priority());
 500 }
 501
 502 inline bool
 503 operator>(const Event &l, const Event &r)
 504 {
 505     return l.when() > r.when() ||
 506         (l.when() == r.when() && l.priority() > r.priority());
 507 }
 508
 509 inline bool
 510 operator<=(const Event &l, const Event &r)
 511 {
 512     return l.when() < r.when() ||
 513         (l.when() == r.when() && l.priority() <= r.priority());
 514 }
 515 inline bool
 516 operator>=(const Event &l, const Event &r)
 517 {
 518     return l.when() > r.when() ||
 519         (l.when() == r.when() && l.priority() >= r.priority());
 520 }
 521
 522 inline bool
 523 operator==(const Event &l, const Event &r)
 524 {
 525     return l.when() == r.when() && l.priority() == r.priority();
 526 }
 527
 528 inline bool
 529 operator!=(const Event &l, const Event &r)
 530 {
 531     return l.when() != r.when() || l.priority() != r.priority();
 532 }
 533 #endif
 534
 535 #endif // __SIM_EVENTQ_HH__