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