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