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