eventq.hh revision 10249
1/* 2 * Copyright (c) 2000-2005 The Regents of The University of Michigan 3 * Copyright (c) 2013 Advanced Micro Devices, Inc. 4 * Copyright (c) 2013 Mark D. Hill and David A. Wood 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are 9 * met: redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer; 11 * redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution; 14 * neither the name of the copyright holders nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * Authors: Steve Reinhardt 31 * Nathan Binkert 32 */ 33 34/* @file 35 * EventQueue interfaces 36 */ 37 38#ifndef __SIM_EVENTQ_HH__ 39#define __SIM_EVENTQ_HH__ 40 41#include <algorithm> 42#include <cassert> 43#include <climits> 44#include <iosfwd> 45#include <mutex> 46#include <string> 47 48#include "base/flags.hh" 49#include "base/misc.hh" 50#include "base/types.hh" 51#include "debug/Event.hh" 52#include "sim/serialize.hh" 53 54class EventQueue; // forward declaration 55class BaseGlobalEvent; 56 57//! Simulation Quantum for multiple eventq simulation. 58//! The quantum value is the period length after which the queues 59//! synchronize themselves with each other. This means that any 60//! event to scheduled on Queue A which is generated by an event on 61//! Queue B should be at least simQuantum ticks away in future. 62extern Tick simQuantum; 63 64//! Current number of allocated main event queues. 65extern uint32_t numMainEventQueues; 66 67//! Array for main event queues. 68extern std::vector<EventQueue *> mainEventQueue; 69 70#ifndef SWIG 71//! The current event queue for the running thread. Access to this queue 72//! does not require any locking from the thread. 73 74extern __thread EventQueue *_curEventQueue; 75 76#endif 77 78//! Current mode of execution: parallel / serial 79extern bool inParallelMode; 80 81//! Function for returning eventq queue for the provided 82//! index. The function allocates a new queue in case one 83//! does not exist for the index, provided that the index 84//! is with in bounds. 85EventQueue *getEventQueue(uint32_t index); 86 87inline EventQueue *curEventQueue() { return _curEventQueue; } 88inline void curEventQueue(EventQueue *q) { _curEventQueue = q; } 89 90/** 91 * Common base class for Event and GlobalEvent, so they can share flag 92 * and priority definitions and accessor functions. This class should 93 * not be used directly. 94 */ 95class EventBase 96{ 97 protected: 98 typedef unsigned short FlagsType; 99 typedef ::Flags<FlagsType> Flags; 100 101 static const FlagsType PublicRead = 0x003f; // public readable flags 102 static const FlagsType PublicWrite = 0x001d; // public writable flags 103 static const FlagsType Squashed = 0x0001; // has been squashed 104 static const FlagsType Scheduled = 0x0002; // has been scheduled 105 static const FlagsType AutoDelete = 0x0004; // delete after dispatch 106 static const FlagsType AutoSerialize = 0x0008; // must be serialized 107 static const FlagsType IsExitEvent = 0x0010; // special exit event 108 static const FlagsType IsMainQueue = 0x0020; // on main event queue 109 static const FlagsType Initialized = 0x7a40; // somewhat random bits 110 static const FlagsType InitMask = 0xffc0; // mask for init bits 111 112 public: 113 typedef int8_t Priority; 114 115 /// Event priorities, to provide tie-breakers for events scheduled 116 /// at the same cycle. Most events are scheduled at the default 117 /// priority; these values are used to control events that need to 118 /// be ordered within a cycle. 119 120 /// Minimum priority 121 static const Priority Minimum_Pri = SCHAR_MIN; 122 123 /// If we enable tracing on a particular cycle, do that as the 124 /// very first thing so we don't miss any of the events on 125 /// that cycle (even if we enter the debugger). 126 static const Priority Debug_Enable_Pri = -101; 127 128 /// Breakpoints should happen before anything else (except 129 /// enabling trace output), so we don't miss any action when 130 /// debugging. 131 static const Priority Debug_Break_Pri = -100; 132 133 /// CPU switches schedule the new CPU's tick event for the 134 /// same cycle (after unscheduling the old CPU's tick event). 135 /// The switch needs to come before any tick events to make 136 /// sure we don't tick both CPUs in the same cycle. 137 static const Priority CPU_Switch_Pri = -31; 138 139 /// For some reason "delayed" inter-cluster writebacks are 140 /// scheduled before regular writebacks (which have default 141 /// priority). Steve? 142 static const Priority Delayed_Writeback_Pri = -1; 143 144 /// Default is zero for historical reasons. 145 static const Priority Default_Pri = 0; 146 147 /// DVFS update event leads to stats dump therefore given a lower priority 148 /// to ensure all relevant states have been updated 149 static const Priority DVFS_Update_Pri = 31; 150 151 /// Serailization needs to occur before tick events also, so 152 /// that a serialize/unserialize is identical to an on-line 153 /// CPU switch. 154 static const Priority Serialize_Pri = 32; 155 156 /// CPU ticks must come after other associated CPU events 157 /// (such as writebacks). 158 static const Priority CPU_Tick_Pri = 50; 159 160 /// Statistics events (dump, reset, etc.) come after 161 /// everything else, but before exit. 162 static const Priority Stat_Event_Pri = 90; 163 164 /// Progress events come at the end. 165 static const Priority Progress_Event_Pri = 95; 166 167 /// If we want to exit on this cycle, it's the very last thing 168 /// we do. 169 static const Priority Sim_Exit_Pri = 100; 170 171 /// Maximum priority 172 static const Priority Maximum_Pri = SCHAR_MAX; 173}; 174 175/* 176 * An item on an event queue. The action caused by a given 177 * event is specified by deriving a subclass and overriding the 178 * process() member function. 179 * 180 * Caution, the order of members is chosen to maximize data packing. 181 */ 182class Event : public EventBase, public Serializable 183{ 184 friend class EventQueue; 185 186 private: 187 // The event queue is now a linked list of linked lists. The 188 // 'nextBin' pointer is to find the bin, where a bin is defined as 189 // when+priority. All events in the same bin will be stored in a 190 // second linked list (a stack) maintained by the 'nextInBin' 191 // pointer. The list will be accessed in LIFO order. The end 192 // result is that the insert/removal in 'nextBin' is 193 // linear/constant, and the lookup/removal in 'nextInBin' is 194 // constant/constant. Hopefully this is a significant improvement 195 // over the current fully linear insertion. 196 Event *nextBin; 197 Event *nextInBin; 198 199 static Event *insertBefore(Event *event, Event *curr); 200 static Event *removeItem(Event *event, Event *last); 201 202 Tick _when; //!< timestamp when event should be processed 203 Priority _priority; //!< event priority 204 Flags flags; 205 206#ifndef NDEBUG 207 /// Global counter to generate unique IDs for Event instances 208 static Counter instanceCounter; 209 210 /// This event's unique ID. We can also use pointer values for 211 /// this but they're not consistent across runs making debugging 212 /// more difficult. Thus we use a global counter value when 213 /// debugging. 214 Counter instance; 215 216 /// queue to which this event belongs (though it may or may not be 217 /// scheduled on this queue yet) 218 EventQueue *queue; 219#endif 220 221#ifdef EVENTQ_DEBUG 222 Tick whenCreated; //!< time created 223 Tick whenScheduled; //!< time scheduled 224#endif 225 226 void 227 setWhen(Tick when, EventQueue *q) 228 { 229 _when = when; 230#ifndef NDEBUG 231 queue = q; 232#endif 233#ifdef EVENTQ_DEBUG 234 whenScheduled = curTick(); 235#endif 236 } 237 238 bool 239 initialized() const 240 { 241 return this && (flags & InitMask) == Initialized; 242 } 243 244 protected: 245 /// Accessor for flags. 246 Flags 247 getFlags() const 248 { 249 return flags & PublicRead; 250 } 251 252 bool 253 isFlagSet(Flags _flags) const 254 { 255 assert(_flags.noneSet(~PublicRead)); 256 return flags.isSet(_flags); 257 } 258 259 /// Accessor for flags. 260 void 261 setFlags(Flags _flags) 262 { 263 assert(_flags.noneSet(~PublicWrite)); 264 flags.set(_flags); 265 } 266 267 void 268 clearFlags(Flags _flags) 269 { 270 assert(_flags.noneSet(~PublicWrite)); 271 flags.clear(_flags); 272 } 273 274 void 275 clearFlags() 276 { 277 flags.clear(PublicWrite); 278 } 279 280 // This function isn't really useful if TRACING_ON is not defined 281 virtual void trace(const char *action); //!< trace event activity 282 283 public: 284 285 /* 286 * Event constructor 287 * @param queue that the event gets scheduled on 288 */ 289 Event(Priority p = Default_Pri, Flags f = 0) 290 : nextBin(NULL), nextInBin(NULL), _priority(p), 291 flags(Initialized | f) 292 { 293 assert(f.noneSet(~PublicWrite)); 294#ifndef NDEBUG 295 instance = ++instanceCounter; 296 queue = NULL; 297#endif 298#ifdef EVENTQ_DEBUG 299 whenCreated = curTick(); 300 whenScheduled = 0; 301#endif 302 } 303 304 virtual ~Event(); 305 virtual const std::string name() const; 306 307 /// Return a C string describing the event. This string should 308 /// *not* be dynamically allocated; just a const char array 309 /// describing the event class. 310 virtual const char *description() const; 311 312 /// Dump the current event data 313 void dump() const; 314 315 public: 316 /* 317 * This member function is invoked when the event is processed 318 * (occurs). There is no default implementation; each subclass 319 * must provide its own implementation. The event is not 320 * automatically deleted after it is processed (to allow for 321 * statically allocated event objects). 322 * 323 * If the AutoDestroy flag is set, the object is deleted once it 324 * is processed. 325 */ 326 virtual void process() = 0; 327 328 /// Determine if the current event is scheduled 329 bool scheduled() const { return flags.isSet(Scheduled); } 330 331 /// Squash the current event 332 void squash() { flags.set(Squashed); } 333 334 /// Check whether the event is squashed 335 bool squashed() const { return flags.isSet(Squashed); } 336 337 /// See if this is a SimExitEvent (without resorting to RTTI) 338 bool isExitEvent() const { return flags.isSet(IsExitEvent); } 339 340 /// Get the time that the event is scheduled 341 Tick when() const { return _when; } 342 343 /// Get the event priority 344 Priority priority() const { return _priority; } 345 346 //! If this is part of a GlobalEvent, return the pointer to the 347 //! Global Event. By default, there is no GlobalEvent, so return 348 //! NULL. (Overridden in GlobalEvent::BarrierEvent.) 349 virtual BaseGlobalEvent *globalEvent() { return NULL; } 350 351#ifndef SWIG 352 virtual void serialize(std::ostream &os); 353 virtual void unserialize(Checkpoint *cp, const std::string §ion); 354 355 //! This function is required to support restoring from checkpoints 356 //! when running with multiple queues. Since we still have not thrashed 357 //! out all the details on checkpointing, this function is most likely 358 //! to be revisited in future. 359 virtual void unserialize(Checkpoint *cp, const std::string §ion, 360 EventQueue *eventq); 361#endif 362}; 363 364#ifndef SWIG 365inline bool 366operator<(const Event &l, const Event &r) 367{ 368 return l.when() < r.when() || 369 (l.when() == r.when() && l.priority() < r.priority()); 370} 371 372inline bool 373operator>(const Event &l, const Event &r) 374{ 375 return l.when() > r.when() || 376 (l.when() == r.when() && l.priority() > r.priority()); 377} 378 379inline bool 380operator<=(const Event &l, const Event &r) 381{ 382 return l.when() < r.when() || 383 (l.when() == r.when() && l.priority() <= r.priority()); 384} 385inline bool 386operator>=(const Event &l, const Event &r) 387{ 388 return l.when() > r.when() || 389 (l.when() == r.when() && l.priority() >= r.priority()); 390} 391 392inline bool 393operator==(const Event &l, const Event &r) 394{ 395 return l.when() == r.when() && l.priority() == r.priority(); 396} 397 398inline bool 399operator!=(const Event &l, const Event &r) 400{ 401 return l.when() != r.when() || l.priority() != r.priority(); 402} 403#endif 404 405/** 406 * Queue of events sorted in time order 407 * 408 * Events are scheduled (inserted into the event queue) using the 409 * schedule() method. This method either inserts a <i>synchronous</i> 410 * or <i>asynchronous</i> event. 411 * 412 * Synchronous events are scheduled using schedule() method with the 413 * argument 'global' set to false (default). This should only be done 414 * from a thread holding the event queue lock 415 * (EventQueue::service_mutex). The lock is always held when an event 416 * handler is called, it can therefore always insert events into its 417 * own event queue unless it voluntarily releases the lock. 418 * 419 * Events can be scheduled across thread (and event queue borders) by 420 * either scheduling asynchronous events or taking the target event 421 * queue's lock. However, the lock should <i>never</i> be taken 422 * directly since this is likely to cause deadlocks. Instead, code 423 * that needs to schedule events in other event queues should 424 * temporarily release its own queue and lock the new queue. This 425 * prevents deadlocks since a single thread never owns more than one 426 * event queue lock. This functionality is provided by the 427 * ScopedMigration helper class. Note that temporarily migrating 428 * between event queues can make the simulation non-deterministic, it 429 * should therefore be limited to cases where that can be tolerated 430 * (e.g., handling asynchronous IO or fast-forwarding in KVM). 431 * 432 * Asynchronous events can also be scheduled using the normal 433 * schedule() method with the 'global' parameter set to true. Unlike 434 * the previous queue migration strategy, this strategy is fully 435 * deterministic. This causes the event to be inserted in a separate 436 * queue of asynchronous events (async_queue), which is merged main 437 * event queue at the end of each simulation quantum (by calling the 438 * handleAsyncInsertions() method). Note that this implies that such 439 * events must happen at least one simulation quantum into the future, 440 * otherwise they risk being scheduled in the past by 441 * handleAsyncInsertions(). 442 */ 443class EventQueue : public Serializable 444{ 445 private: 446 std::string objName; 447 Event *head; 448 Tick _curTick; 449 450 //! Mutex to protect async queue. 451 std::mutex *async_queue_mutex; 452 453 //! List of events added by other threads to this event queue. 454 std::list<Event*> async_queue; 455 456 /** 457 * Lock protecting event handling. 458 * 459 * This lock is always taken when servicing events. It is assumed 460 * that the thread scheduling new events (not asynchronous events 461 * though) have taken this lock. This is normally done by 462 * serviceOne() since new events are typically scheduled as a 463 * response to an earlier event. 464 * 465 * This lock is intended to be used to temporarily steal an event 466 * queue to support inter-thread communication when some 467 * deterministic timing can be sacrificed for speed. For example, 468 * the KVM CPU can use this support to access devices running in a 469 * different thread. 470 * 471 * @see EventQueue::ScopedMigration. 472 * @see EventQueue::ScopedRelease 473 * @see EventQueue::lock() 474 * @see EventQueue::unlock() 475 */ 476 std::mutex service_mutex; 477 478 //! Insert / remove event from the queue. Should only be called 479 //! by thread operating this queue. 480 void insert(Event *event); 481 void remove(Event *event); 482 483 //! Function for adding events to the async queue. The added events 484 //! are added to main event queue later. Threads, other than the 485 //! owning thread, should call this function instead of insert(). 486 void asyncInsert(Event *event); 487 488 EventQueue(const EventQueue &); 489 490 public: 491#ifndef SWIG 492 /** 493 * Temporarily migrate execution to a different event queue. 494 * 495 * An instance of this class temporarily migrates execution to a 496 * different event queue by releasing the current queue, locking 497 * the new queue, and updating curEventQueue(). This can, for 498 * example, be useful when performing IO across thread event 499 * queues when timing is not crucial (e.g., during fast 500 * forwarding). 501 */ 502 class ScopedMigration 503 { 504 public: 505 ScopedMigration(EventQueue *_new_eq) 506 : new_eq(*_new_eq), old_eq(*curEventQueue()) 507 { 508 old_eq.unlock(); 509 new_eq.lock(); 510 curEventQueue(&new_eq); 511 } 512 513 ~ScopedMigration() 514 { 515 new_eq.unlock(); 516 old_eq.lock(); 517 curEventQueue(&old_eq); 518 } 519 520 private: 521 EventQueue &new_eq; 522 EventQueue &old_eq; 523 }; 524 525 /** 526 * Temporarily release the event queue service lock. 527 * 528 * There are cases where it is desirable to temporarily release 529 * the event queue lock to prevent deadlocks. For example, when 530 * waiting on the global barrier, we need to release the lock to 531 * prevent deadlocks from happening when another thread tries to 532 * temporarily take over the event queue waiting on the barrier. 533 */ 534 class ScopedRelease 535 { 536 public: 537 ScopedRelease(EventQueue *_eq) 538 : eq(*_eq) 539 { 540 eq.unlock(); 541 } 542 543 ~ScopedRelease() 544 { 545 eq.lock(); 546 } 547 548 private: 549 EventQueue &eq; 550 }; 551#endif 552 553 EventQueue(const std::string &n); 554 555 virtual const std::string name() const { return objName; } 556 void name(const std::string &st) { objName = st; } 557 558 //! Schedule the given event on this queue. Safe to call from any 559 //! thread. 560 void schedule(Event *event, Tick when, bool global = false); 561 562 //! Deschedule the specified event. Should be called only from the 563 //! owning thread. 564 void deschedule(Event *event); 565 566 //! Reschedule the specified event. Should be called only from 567 //! the owning thread. 568 void reschedule(Event *event, Tick when, bool always = false); 569 570 Tick nextTick() const { return head->when(); } 571 void setCurTick(Tick newVal) { _curTick = newVal; } 572 Tick getCurTick() { return _curTick; } 573 574 Event *serviceOne(); 575 576 // process all events up to the given timestamp. we inline a 577 // quick test to see if there are any events to process; if so, 578 // call the internal out-of-line version to process them all. 579 void 580 serviceEvents(Tick when) 581 { 582 while (!empty()) { 583 if (nextTick() > when) 584 break; 585 586 /** 587 * @todo this assert is a good bug catcher. I need to 588 * make it true again. 589 */ 590 //assert(head->when() >= when && "event scheduled in the past"); 591 serviceOne(); 592 } 593 594 setCurTick(when); 595 } 596 597 // return true if no events are queued 598 bool empty() const { return head == NULL; } 599 600 void dump() const; 601 602 bool debugVerify() const; 603 604 //! Function for moving events from the async_queue to the main queue. 605 void handleAsyncInsertions(); 606 607 /** 608 * function for replacing the head of the event queue, so that a 609 * different set of events can run without disturbing events that have 610 * already been scheduled. Already scheduled events can be processed 611 * by replacing the original head back. 612 * USING THIS FUNCTION CAN BE DANGEROUS TO THE HEALTH OF THE SIMULATOR. 613 * NOT RECOMMENDED FOR USE. 614 */ 615 Event* replaceHead(Event* s); 616 617 /**@{*/ 618 /** 619 * Provide an interface for locking/unlocking the event queue. 620 * 621 * @warn Do NOT use these methods directly unless you really know 622 * what you are doing. Incorrect use can easily lead to simulator 623 * deadlocks. 624 * 625 * @see EventQueue::ScopedMigration. 626 * @see EventQueue::ScopedRelease 627 * @see EventQueue 628 */ 629 void lock() { service_mutex.lock(); } 630 void unlock() { service_mutex.unlock(); } 631 /**@}*/ 632 633#ifndef SWIG 634 virtual void serialize(std::ostream &os); 635 virtual void unserialize(Checkpoint *cp, const std::string §ion); 636#endif 637}; 638 639void dumpMainQueue(); 640 641#ifndef SWIG 642class EventManager 643{ 644 protected: 645 /** A pointer to this object's event queue */ 646 EventQueue *eventq; 647 648 public: 649 EventManager(EventManager &em) : eventq(em.eventq) {} 650 EventManager(EventManager *em) : eventq(em->eventq) {} 651 EventManager(EventQueue *eq) : eventq(eq) {} 652 653 EventQueue * 654 eventQueue() const 655 { 656 return eventq; 657 } 658 659 void 660 schedule(Event &event, Tick when) 661 { 662 eventq->schedule(&event, when); 663 } 664 665 void 666 deschedule(Event &event) 667 { 668 eventq->deschedule(&event); 669 } 670 671 void 672 reschedule(Event &event, Tick when, bool always = false) 673 { 674 eventq->reschedule(&event, when, always); 675 } 676 677 void 678 schedule(Event *event, Tick when) 679 { 680 eventq->schedule(event, when); 681 } 682 683 void 684 deschedule(Event *event) 685 { 686 eventq->deschedule(event); 687 } 688 689 void 690 reschedule(Event *event, Tick when, bool always = false) 691 { 692 eventq->reschedule(event, when, always); 693 } 694 695 void setCurTick(Tick newVal) { eventq->setCurTick(newVal); } 696}; 697 698template <class T, void (T::* F)()> 699void 700DelayFunction(EventQueue *eventq, Tick when, T *object) 701{ 702 class DelayEvent : public Event 703 { 704 private: 705 T *object; 706 707 public: 708 DelayEvent(T *o) 709 : Event(Default_Pri, AutoDelete), object(o) 710 { } 711 void process() { (object->*F)(); } 712 const char *description() const { return "delay"; } 713 }; 714 715 eventq->schedule(new DelayEvent(object), when); 716} 717 718template <class T, void (T::* F)()> 719class EventWrapper : public Event 720{ 721 private: 722 T *object; 723 724 public: 725 EventWrapper(T *obj, bool del = false, Priority p = Default_Pri) 726 : Event(p), object(obj) 727 { 728 if (del) 729 setFlags(AutoDelete); 730 } 731 732 EventWrapper(T &obj, bool del = false, Priority p = Default_Pri) 733 : Event(p), object(&obj) 734 { 735 if (del) 736 setFlags(AutoDelete); 737 } 738 739 void process() { (object->*F)(); } 740 741 const std::string 742 name() const 743 { 744 return object->name() + ".wrapped_event"; 745 } 746 747 const char *description() const { return "EventWrapped"; } 748}; 749#endif 750 751#endif // __SIM_EVENTQ_HH__ 752