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