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