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