eventq.hh revision 5605
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 213 ~Event() 214 { 215 } 216 217 virtual const std::string 218 name() const 219 { 220#ifndef NDEBUG 221 return csprintf("Event_%d", instance); 222#else 223 return csprintf("Event_%x", (uintptr_t)this); 224#endif 225 } 226 227 /// Return a C string describing the event. This string should 228 /// *not* be dynamically allocated; just a const char array 229 /// describing the event class. 230 virtual const char *description() const; 231 232 /// Dump the current event data 233 void dump() const; 234 235 public: 236 /* 237 * This member function is invoked when the event is processed 238 * (occurs). There is no default implementation; each subclass 239 * must provide its own implementation. The event is not 240 * automatically deleted after it is processed (to allow for 241 * statically allocated event objects). 242 * 243 * If the AutoDestroy flag is set, the object is deleted once it 244 * is processed. 245 */ 246 virtual void process() = 0; 247 248 /// Determine if the current event is scheduled 249 bool scheduled() const { return getFlags(Scheduled); } 250 251 /// Squash the current event 252 void squash() { setFlags(Squashed); } 253 254 /// Check whether the event is squashed 255 bool squashed() const { return getFlags(Squashed); } 256 257 /// See if this is a SimExitEvent (without resorting to RTTI) 258 bool isExitEvent() const { return getFlags(IsExitEvent); } 259 260 /// Get the time that the event is scheduled 261 Tick when() const { return _when; } 262 263 /// Get the event priority 264 int priority() const { return _priority; } 265 266#ifndef SWIG 267 struct priority_compare 268 : public std::binary_function<Event *, Event *, bool> 269 { 270 bool 271 operator()(const Event *l, const Event *r) const 272 { 273 return l->when() >= r->when() || l->priority() >= r->priority(); 274 } 275 }; 276 277 virtual void serialize(std::ostream &os); 278 virtual void unserialize(Checkpoint *cp, const std::string §ion); 279#endif 280}; 281 282/* 283 * Queue of events sorted in time order 284 */ 285class EventQueue : public Serializable 286{ 287 private: 288 std::string objName; 289 Event *head; 290 291 void insert(Event *event); 292 void remove(Event *event); 293 294 public: 295 EventQueue(const std::string &n) 296 : objName(n), head(NULL) 297 {} 298 299 virtual const std::string name() const { return objName; } 300 301 // schedule the given event on this queue 302 void schedule(Event *ev, Tick when); 303 void deschedule(Event *ev); 304 void reschedule(Event *ev, Tick when, bool always = false); 305 306 Tick nextTick() const { return head->when(); } 307 Event *serviceOne(); 308 309 // process all events up to the given timestamp. we inline a 310 // quick test to see if there are any events to process; if so, 311 // call the internal out-of-line version to process them all. 312 void 313 serviceEvents(Tick when) 314 { 315 while (!empty()) { 316 if (nextTick() > when) 317 break; 318 319 /** 320 * @todo this assert is a good bug catcher. I need to 321 * make it true again. 322 */ 323 //assert(head->when() >= when && "event scheduled in the past"); 324 serviceOne(); 325 } 326 } 327 328 // default: process all events up to 'now' (curTick) 329 void serviceEvents() { serviceEvents(curTick); } 330 331 // return true if no events are queued 332 bool empty() const { return head == NULL; } 333 334 void dump() const; 335 336 Tick nextEventTime() { return empty() ? curTick : head->when(); } 337 338 bool debugVerify() const; 339 340#ifndef SWIG 341 virtual void serialize(std::ostream &os); 342 virtual void unserialize(Checkpoint *cp, const std::string §ion); 343#endif 344}; 345 346#ifndef SWIG 347class EventManager 348{ 349 protected: 350 /** A pointer to this object's event queue */ 351 EventQueue *eventq; 352 353 public: 354 EventManager(EventManager &em) : eventq(em.queue()) {} 355 EventManager(EventManager *em) : eventq(em ? em->queue() : NULL) {} 356 EventManager(EventQueue *eq) : eventq(eq) {} 357 358 EventQueue * 359 queue() const 360 { 361 return eventq; 362 } 363 364 void 365 schedule(Event &event, Tick when) 366 { 367 eventq->schedule(&event, when); 368 } 369 370 void 371 deschedule(Event &event) 372 { 373 eventq->deschedule(&event); 374 } 375 376 void 377 reschedule(Event &event, Tick when, bool always = false) 378 { 379 eventq->reschedule(&event, when, always); 380 } 381 382 void 383 schedule(Event *event, Tick when) 384 { 385 eventq->schedule(event, when); 386 } 387 388 void 389 deschedule(Event *event) 390 { 391 eventq->deschedule(event); 392 } 393 394 void 395 reschedule(Event *event, Tick when, bool always = false) 396 { 397 eventq->reschedule(event, when, always); 398 } 399}; 400 401template <class T, void (T::* F)()> 402void 403DelayFunction(EventQueue *eventq, Tick when, T *object) 404{ 405 class DelayEvent : public Event 406 { 407 private: 408 T *object; 409 410 public: 411 DelayEvent(T *o) 412 : object(o) 413 { setFlags(this->AutoDestroy); } 414 void process() { (object->*F)(); } 415 const char *description() const { return "delay"; } 416 }; 417 418 eventq->schedule(new DelayEvent(object), when); 419} 420 421template <class T, void (T::* F)()> 422class EventWrapper : public Event 423{ 424 private: 425 T *object; 426 427 public: 428 EventWrapper(T *obj, bool del = false, Priority p = Default_Pri) 429 : Event(p), object(obj) 430 { 431 if (del) 432 setFlags(AutoDelete); 433 } 434 435 void process() { (object->*F)(); } 436}; 437 438inline void 439EventQueue::schedule(Event *event, Tick when) 440{ 441 assert(when >= curTick); 442 assert(!event->scheduled()); 443 444 event->setWhen(when, this); 445 insert(event); 446 event->setFlags(Event::Scheduled); 447 if (this == &mainEventQueue) 448 event->setFlags(Event::IsMainQueue); 449 else 450 event->clearFlags(Event::IsMainQueue); 451 452 if (DTRACE(Event)) 453 event->trace("scheduled"); 454} 455 456inline void 457EventQueue::deschedule(Event *event) 458{ 459 assert(event->scheduled()); 460 461 remove(event); 462 463 event->clearFlags(Event::Squashed); 464 event->clearFlags(Event::Scheduled); 465 466 if (event->getFlags(Event::AutoDelete)) 467 delete event; 468 469 if (DTRACE(Event)) 470 event->trace("descheduled"); 471} 472 473inline void 474EventQueue::reschedule(Event *event, Tick when, bool always) 475{ 476 assert(when >= curTick); 477 assert(always || event->scheduled()); 478 479 if (event->scheduled()) 480 remove(event); 481 482 event->setWhen(when, this); 483 insert(event); 484 event->clearFlags(Event::Squashed); 485 event->setFlags(Event::Scheduled); 486 if (this == &mainEventQueue) 487 event->setFlags(Event::IsMainQueue); 488 else 489 event->clearFlags(Event::IsMainQueue); 490 491 if (DTRACE(Event)) 492 event->trace("rescheduled"); 493} 494 495inline bool 496operator<(const Event &l, const Event &r) 497{ 498 return l.when() < r.when() || 499 (l.when() == r.when() && l.priority() < r.priority()); 500} 501 502inline bool 503operator>(const Event &l, const Event &r) 504{ 505 return l.when() > r.when() || 506 (l.when() == r.when() && l.priority() > r.priority()); 507} 508 509inline bool 510operator<=(const Event &l, const Event &r) 511{ 512 return l.when() < r.when() || 513 (l.when() == r.when() && l.priority() <= r.priority()); 514} 515inline bool 516operator>=(const Event &l, const Event &r) 517{ 518 return l.when() > r.when() || 519 (l.when() == r.when() && l.priority() >= r.priority()); 520} 521 522inline bool 523operator==(const Event &l, const Event &r) 524{ 525 return l.when() == r.when() && l.priority() == r.priority(); 526} 527 528inline bool 529operator!=(const Event &l, const Event &r) 530{ 531 return l.when() != r.when() || l.priority() != r.priority(); 532} 533#endif 534 535#endif // __SIM_EVENTQ_HH__ 536