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