eventq.hh revision 9983:2cce74fe359e
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 */ 404class EventQueue : public Serializable 405{ 406 private: 407 std::string objName; 408 Event *head; 409 Tick _curTick; 410 411 //! Mutex to protect async queue. 412 std::mutex *async_queue_mutex; 413 414 //! List of events added by other threads to this event queue. 415 std::list<Event*> async_queue; 416 417 //! Insert / remove event from the queue. Should only be called 418 //! by thread operating this queue. 419 void insert(Event *event); 420 void remove(Event *event); 421 422 //! Function for adding events to the async queue. The added events 423 //! are added to main event queue later. Threads, other than the 424 //! owning thread, should call this function instead of insert(). 425 void asyncInsert(Event *event); 426 427 EventQueue(const EventQueue &); 428 429 public: 430 EventQueue(const std::string &n); 431 432 virtual const std::string name() const { return objName; } 433 void name(const std::string &st) { objName = st; } 434 435 //! Schedule the given event on this queue. Safe to call from any 436 //! thread. 437 void schedule(Event *event, Tick when, bool global = false); 438 439 //! Deschedule the specified event. Should be called only from the 440 //! owning thread. 441 void deschedule(Event *event); 442 443 //! Reschedule the specified event. Should be called only from 444 //! the owning thread. 445 void reschedule(Event *event, Tick when, bool always = false); 446 447 Tick nextTick() const { return head->when(); } 448 void setCurTick(Tick newVal) { _curTick = newVal; } 449 Tick getCurTick() { return _curTick; } 450 451 Event *serviceOne(); 452 453 // process all events up to the given timestamp. we inline a 454 // quick test to see if there are any events to process; if so, 455 // call the internal out-of-line version to process them all. 456 void 457 serviceEvents(Tick when) 458 { 459 while (!empty()) { 460 if (nextTick() > when) 461 break; 462 463 /** 464 * @todo this assert is a good bug catcher. I need to 465 * make it true again. 466 */ 467 //assert(head->when() >= when && "event scheduled in the past"); 468 serviceOne(); 469 } 470 471 setCurTick(when); 472 } 473 474 // return true if no events are queued 475 bool empty() const { return head == NULL; } 476 477 void dump() const; 478 479 bool debugVerify() const; 480 481 //! Function for moving events from the async_queue to the main queue. 482 void handleAsyncInsertions(); 483 484 /** 485 * function for replacing the head of the event queue, so that a 486 * different set of events can run without disturbing events that have 487 * already been scheduled. Already scheduled events can be processed 488 * by replacing the original head back. 489 * USING THIS FUNCTION CAN BE DANGEROUS TO THE HEALTH OF THE SIMULATOR. 490 * NOT RECOMMENDED FOR USE. 491 */ 492 Event* replaceHead(Event* s); 493 494#ifndef SWIG 495 virtual void serialize(std::ostream &os); 496 virtual void unserialize(Checkpoint *cp, const std::string §ion); 497#endif 498}; 499 500void dumpMainQueue(); 501 502#ifndef SWIG 503class EventManager 504{ 505 protected: 506 /** A pointer to this object's event queue */ 507 EventQueue *eventq; 508 509 public: 510 EventManager(EventManager &em) : eventq(em.eventq) {} 511 EventManager(EventManager *em) : eventq(em->eventq) {} 512 EventManager(EventQueue *eq) : eventq(eq) {} 513 514 EventQueue * 515 eventQueue() const 516 { 517 return eventq; 518 } 519 520 void 521 schedule(Event &event, Tick when) 522 { 523 eventq->schedule(&event, when); 524 } 525 526 void 527 deschedule(Event &event) 528 { 529 eventq->deschedule(&event); 530 } 531 532 void 533 reschedule(Event &event, Tick when, bool always = false) 534 { 535 eventq->reschedule(&event, when, always); 536 } 537 538 void 539 schedule(Event *event, Tick when) 540 { 541 eventq->schedule(event, when); 542 } 543 544 void 545 deschedule(Event *event) 546 { 547 eventq->deschedule(event); 548 } 549 550 void 551 reschedule(Event *event, Tick when, bool always = false) 552 { 553 eventq->reschedule(event, when, always); 554 } 555 556 void setCurTick(Tick newVal) { eventq->setCurTick(newVal); } 557}; 558 559template <class T, void (T::* F)()> 560void 561DelayFunction(EventQueue *eventq, Tick when, T *object) 562{ 563 class DelayEvent : public Event 564 { 565 private: 566 T *object; 567 568 public: 569 DelayEvent(T *o) 570 : Event(Default_Pri, AutoDelete), object(o) 571 { } 572 void process() { (object->*F)(); } 573 const char *description() const { return "delay"; } 574 }; 575 576 eventq->schedule(new DelayEvent(object), when); 577} 578 579template <class T, void (T::* F)()> 580class EventWrapper : public Event 581{ 582 private: 583 T *object; 584 585 public: 586 EventWrapper(T *obj, bool del = false, Priority p = Default_Pri) 587 : Event(p), object(obj) 588 { 589 if (del) 590 setFlags(AutoDelete); 591 } 592 593 EventWrapper(T &obj, bool del = false, Priority p = Default_Pri) 594 : Event(p), object(&obj) 595 { 596 if (del) 597 setFlags(AutoDelete); 598 } 599 600 void process() { (object->*F)(); } 601 602 const std::string 603 name() const 604 { 605 return object->name() + ".wrapped_event"; 606 } 607 608 const char *description() const { return "EventWrapped"; } 609}; 610#endif 611 612#endif // __SIM_EVENTQ_HH__ 613