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