eventq.hh revision 9493:890fc69ba53c
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/flags.hh" 46#include "base/misc.hh" 47#include "base/types.hh" 48#include "debug/Event.hh" 49#include "sim/serialize.hh" 50 51class EventQueue; // forward declaration 52 53extern EventQueue mainEventQueue; 54 55/* 56 * An item on an event queue. The action caused by a given 57 * event is specified by deriving a subclass and overriding the 58 * process() member function. 59 * 60 * Caution, the order of members is chosen to maximize data packing. 61 */ 62class Event : public Serializable 63{ 64 friend class EventQueue; 65 66 protected: 67 typedef unsigned short FlagsType; 68 typedef ::Flags<FlagsType> Flags; 69 70 static const FlagsType PublicRead = 0x003f; // public readable flags 71 static const FlagsType PublicWrite = 0x001d; // public writable flags 72 static const FlagsType Squashed = 0x0001; // has been squashed 73 static const FlagsType Scheduled = 0x0002; // has been scheduled 74 static const FlagsType AutoDelete = 0x0004; // delete after dispatch 75 static const FlagsType AutoSerialize = 0x0008; // must be serialized 76 static const FlagsType IsExitEvent = 0x0010; // special exit event 77 static const FlagsType IsMainQueue = 0x0020; // on main event queue 78 static const FlagsType Initialized = 0x7a40; // somewhat random bits 79 static const FlagsType InitMask = 0xffc0; // mask for init bits 80 81 bool 82 initialized() const 83 { 84 return this && (flags & InitMask) == Initialized; 85 } 86 87 public: 88 typedef int8_t Priority; 89 90 private: 91 // The event queue is now a linked list of linked lists. The 92 // 'nextBin' pointer is to find the bin, where a bin is defined as 93 // when+priority. All events in the same bin will be stored in a 94 // second linked list (a stack) maintained by the 'nextInBin' 95 // pointer. The list will be accessed in LIFO order. The end 96 // result is that the insert/removal in 'nextBin' is 97 // linear/constant, and the lookup/removal in 'nextInBin' is 98 // constant/constant. Hopefully this is a significant improvement 99 // over the current fully linear insertion. 100 Event *nextBin; 101 Event *nextInBin; 102 103 static Event *insertBefore(Event *event, Event *curr); 104 static Event *removeItem(Event *event, Event *last); 105 106 Tick _when; //!< timestamp when event should be processed 107 Priority _priority; //!< event priority 108 Flags flags; 109 110#ifndef NDEBUG 111 /// Global counter to generate unique IDs for Event instances 112 static Counter instanceCounter; 113 114 /// This event's unique ID. We can also use pointer values for 115 /// this but they're not consistent across runs making debugging 116 /// more difficult. Thus we use a global counter value when 117 /// debugging. 118 Counter instance; 119 120 /// queue to which this event belongs (though it may or may not be 121 /// scheduled on this queue yet) 122 EventQueue *queue; 123#endif 124 125#ifdef EVENTQ_DEBUG 126 Tick whenCreated; //!< time created 127 Tick whenScheduled; //!< time scheduled 128#endif 129 130 void 131 setWhen(Tick when, EventQueue *q) 132 { 133 _when = when; 134#ifndef NDEBUG 135 queue = q; 136#endif 137#ifdef EVENTQ_DEBUG 138 whenScheduled = curTick(); 139#endif 140 } 141 142 protected: 143 /// Accessor for flags. 144 Flags 145 getFlags() const 146 { 147 return flags & PublicRead; 148 } 149 150 bool 151 isFlagSet(Flags _flags) const 152 { 153 assert(_flags.noneSet(~PublicRead)); 154 return flags.isSet(_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 187 /// Minimum priority 188 static const Priority Minimum_Pri = SCHAR_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 static const Priority 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 static const Priority 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 static const Priority 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 static const Priority Delayed_Writeback_Pri = -1; 210 211 /// Default is zero for historical reasons. 212 static const Priority 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 static const Priority Serialize_Pri = 32; 218 219 /// CPU ticks must come after other associated CPU events 220 /// (such as writebacks). 221 static const Priority CPU_Tick_Pri = 50; 222 223 /// Statistics events (dump, reset, etc.) come after 224 /// everything else, but before exit. 225 static const Priority Stat_Event_Pri = 90; 226 227 /// Progress events come at the end. 228 static const Priority Progress_Event_Pri = 95; 229 230 /// If we want to exit on this cycle, it's the very last thing 231 /// we do. 232 static const Priority Sim_Exit_Pri = 100; 233 234 /// Maximum priority 235 static const Priority Maximum_Pri = SCHAR_MAX; 236 237 /* 238 * Event constructor 239 * @param queue that the event gets scheduled on 240 */ 241 Event(Priority p = Default_Pri, Flags f = 0) 242 : nextBin(NULL), nextInBin(NULL), _priority(p), 243 flags(Initialized | f) 244 { 245 assert(f.noneSet(~PublicWrite)); 246#ifndef NDEBUG 247 instance = ++instanceCounter; 248 queue = NULL; 249#endif 250#ifdef EVENTQ_DEBUG 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 Priority priority() const { return _priority; } 297 298#ifndef SWIG 299 virtual void serialize(std::ostream &os); 300 virtual void unserialize(Checkpoint *cp, const std::string §ion); 301#endif 302}; 303 304#ifndef SWIG 305inline bool 306operator<(const Event &l, const Event &r) 307{ 308 return l.when() < r.when() || 309 (l.when() == r.when() && l.priority() < r.priority()); 310} 311 312inline bool 313operator>(const Event &l, const Event &r) 314{ 315 return l.when() > r.when() || 316 (l.when() == r.when() && l.priority() > r.priority()); 317} 318 319inline bool 320operator<=(const Event &l, const Event &r) 321{ 322 return l.when() < r.when() || 323 (l.when() == r.when() && l.priority() <= r.priority()); 324} 325inline bool 326operator>=(const Event &l, const Event &r) 327{ 328 return l.when() > r.when() || 329 (l.when() == r.when() && l.priority() >= r.priority()); 330} 331 332inline bool 333operator==(const Event &l, const Event &r) 334{ 335 return l.when() == r.when() && l.priority() == r.priority(); 336} 337 338inline bool 339operator!=(const Event &l, const Event &r) 340{ 341 return l.when() != r.when() || l.priority() != r.priority(); 342} 343#endif 344 345/* 346 * Queue of events sorted in time order 347 */ 348class EventQueue : public Serializable 349{ 350 private: 351 std::string objName; 352 Event *head; 353 Tick _curTick; 354 355 void insert(Event *event); 356 void remove(Event *event); 357 358 EventQueue(const EventQueue &); 359 const EventQueue &operator=(const EventQueue &); 360 361 public: 362 EventQueue(const std::string &n); 363 364 virtual const std::string name() const { return objName; } 365 366 // schedule the given event on this queue 367 void schedule(Event *event, Tick when); 368 void deschedule(Event *event); 369 void reschedule(Event *event, Tick when, bool always = false); 370 371 Tick nextTick() const { return head->when(); } 372 void setCurTick(Tick newVal) { _curTick = newVal; } 373 Tick getCurTick() { return _curTick; } 374 375 Event *serviceOne(); 376 377 // process all events up to the given timestamp. we inline a 378 // quick test to see if there are any events to process; if so, 379 // call the internal out-of-line version to process them all. 380 void 381 serviceEvents(Tick when) 382 { 383 while (!empty()) { 384 if (nextTick() > when) 385 break; 386 387 /** 388 * @todo this assert is a good bug catcher. I need to 389 * make it true again. 390 */ 391 //assert(head->when() >= when && "event scheduled in the past"); 392 serviceOne(); 393 } 394 395 setCurTick(when); 396 } 397 398 // return true if no events are queued 399 bool empty() const { return head == NULL; } 400 401 void dump() const; 402 403 bool debugVerify() const; 404 405 /** 406 * function for replacing the head of the event queue, so that a 407 * different set of events can run without disturbing events that have 408 * already been scheduled. Already scheduled events can be processed 409 * by replacing the original head back. 410 * USING THIS FUNCTION CAN BE DANGEROUS TO THE HEALTH OF THE SIMULATOR. 411 * NOT RECOMMENDED FOR USE. 412 */ 413 Event* replaceHead(Event* s); 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.eventq) {} 430 EventManager(EventManager *em) : eventq(em->eventq) {} 431 EventManager(EventQueue *eq) : eventq(eq) {} 432 433 EventQueue * 434 eventQueue() 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 void setCurTick(Tick newVal) { eventq->setCurTick(newVal); } 476}; 477 478template <class T, void (T::* F)()> 479void 480DelayFunction(EventQueue *eventq, Tick when, T *object) 481{ 482 class DelayEvent : public Event 483 { 484 private: 485 T *object; 486 487 public: 488 DelayEvent(T *o) 489 : Event(Default_Pri, AutoDelete), object(o) 490 { } 491 void process() { (object->*F)(); } 492 const char *description() const { return "delay"; } 493 }; 494 495 eventq->schedule(new DelayEvent(object), when); 496} 497 498template <class T, void (T::* F)()> 499class EventWrapper : public Event 500{ 501 private: 502 T *object; 503 504 public: 505 EventWrapper(T *obj, bool del = false, Priority p = Default_Pri) 506 : Event(p), object(obj) 507 { 508 if (del) 509 setFlags(AutoDelete); 510 } 511 512 EventWrapper(T &obj, bool del = false, Priority p = Default_Pri) 513 : Event(p), object(&obj) 514 { 515 if (del) 516 setFlags(AutoDelete); 517 } 518 519 void process() { (object->*F)(); } 520 521 const std::string 522 name() const 523 { 524 return object->name() + ".wrapped_event"; 525 } 526 527 const char *description() const { return "EventWrapped"; } 528}; 529#endif 530 531#endif // __SIM_EVENTQ_HH__ 532