src/sim/eventq.cc

   1 /*
   2  * Copyright (c) 2000-2005 The Regents of The University of Michigan
   3  * Copyright (c) 2008 The Hewlett-Packard Development Company
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * Authors: Steve Reinhardt
  30  *          Nathan Binkert
  31  *          Steve Raasch
  32  */
  33
  34 #include <cassert>
  35 #include <iostream>
  36 #include <string>
  37 #include <vector>
  38
  39 #include "base/hashmap.hh"
  40 #include "base/misc.hh"
  41 #include "base/trace.hh"
  42 #include "cpu/smt.hh"
  43 #include "sim/core.hh"
  44 #include "sim/eventq.hh"
  45
  46 using namespace std;
  47
  48 //
  49 // Main Event Queue
  50 //
  51 // Events on this queue are processed at the *beginning* of each
  52 // cycle, before the pipeline simulation is performed.
  53 //
  54 EventQueue mainEventQueue("Main Event Queue");
  55
  56 #ifndef NDEBUG
  57 Counter Event::instanceCounter = 0;
  58 #endif
  59
  60 Event::~Event()
  61 {
  62     assert(!scheduled());
  63 }
  64
  65 const std::string
  66 Event::name() const
  67 {
  68 #ifndef NDEBUG
  69     return csprintf("Event_%d", instance);
  70 #else
  71     return csprintf("Event_%x", (uintptr_t)this);
  72 #endif
  73 }
  74
  75
  76 Event *
  77 Event::insertBefore(Event *event, Event *curr)
  78 {
  79     // Either way, event will be the top element in the 'in bin' list
  80     // which is the pointer we need in order to look into the list, so
  81     // we need to insert that into the bin list.
  82     if (!curr || *event < *curr) {
  83         // Insert the event before the current list since it is in the future.
  84         event->nextBin = curr;
  85         event->nextInBin = NULL;
  86     } else {
  87         // Since we're on the correct list, we need to point to the next list
  88         event->nextBin = curr->nextBin;  // curr->nextBin can now become stale
  89
  90         // Insert event at the top of the stack
  91         event->nextInBin = curr;
  92     }
  93
  94     return event;
  95 }
  96
  97 void
  98 EventQueue::insert(Event *event)
  99 {
 100     // Deal with the head case
 101     if (!head || *event <= *head) {
 102         head = Event::insertBefore(event, head);
 103         return;
 104     }
 105
 106     // Figure out either which 'in bin' list we are on, or where a new list
 107     // needs to be inserted
 108     Event *prev = head;
 109     Event *curr = head->nextBin;
 110     while (curr && *curr < *event) {
 111         prev = curr;
 112         curr = curr->nextBin;
 113     }
 114
 115     // Note: this operation may render all nextBin pointers on the
 116     // prev 'in bin' list stale (except for the top one)
 117     prev->nextBin = Event::insertBefore(event, curr);
 118 }
 119
 120 Event *
 121 Event::removeItem(Event *event, Event *top)
 122 {
 123     Event *curr = top;
 124     Event *next = top->nextInBin;
 125
 126     // if we removed the top item, we need to handle things specially
 127     // and just remove the top item, fixing up the next bin pointer of
 128     // the new top item
 129     if (event == top) {
 130         if (!next)
 131             return top->nextBin;
 132         next->nextBin = top->nextBin;
 133         return next;
 134     }
 135
 136     // Since we already checked the current element, we're going to
 137     // keep checking event against the next element.
 138     while (event != next) {
 139         if (!next)
 140             panic("event not found!");
 141
 142         curr = next;
 143         next = next->nextInBin;
 144     }
 145
 146     // remove next from the 'in bin' list since it's what we're looking for
 147     curr->nextInBin = next->nextInBin;
 148     return top;
 149 }
 150
 151 void
 152 EventQueue::remove(Event *event)
 153 {
 154     if (head == NULL)
 155         panic("event not found!");
 156
 157     // deal with an event on the head's 'in bin' list (event has the same
 158     // time as the head)
 159     if (*head == *event) {
 160         head = Event::removeItem(event, head);
 161         return;
 162     }
 163
 164     // Find the 'in bin' list that this event belongs on
 165     Event *prev = head;
 166     Event *curr = head->nextBin;
 167     while (curr && *curr < *event) {
 168         prev = curr;
 169         curr = curr->nextBin;
 170     }
 171
 172     if (!curr || *curr != *event)
 173         panic("event not found!");
 174
 175     // curr points to the top item of the the correct 'in bin' list, when
 176     // we remove an item, it returns the new top item (which may be
 177     // unchanged)
 178     prev->nextBin = Event::removeItem(event, curr);
 179 }
 180
 181 Event *
 182 EventQueue::serviceOne()
 183 {
 184     Event *event = head;
 185     Event *next = head->nextInBin;
 186     event->flags.clear(Event::Scheduled);
 187
 188     if (next) {
 189         // update the next bin pointer since it could be stale
 190         next->nextBin = head->nextBin;
 191
 192         // pop the stack
 193         head = next;
 194     } else {
 195         // this was the only element on the 'in bin' list, so get rid of
 196         // the 'in bin' list and point to the next bin list
 197         head = head->nextBin;
 198     }
 199
 200     // handle action
 201     if (!event->squashed()) {
 202         event->process();
 203         if (event->isExitEvent()) {
 204             assert(!event->flags.isSet(Event::AutoDelete)); // would be silly
 205             return event;
 206         }
 207     } else {
 208         event->flags.clear(Event::Squashed);
 209     }
 210
 211     if (event->flags.isSet(Event::AutoDelete) && !event->scheduled())
 212         delete event;
 213
 214     return NULL;
 215 }
 216
 217 void
 218 Event::serialize(std::ostream &os)
 219 {
 220     SERIALIZE_SCALAR(_when);
 221     SERIALIZE_SCALAR(_priority);
 222     short _flags = flags;
 223     SERIALIZE_SCALAR(_flags);
 224 }
 225
 226 void
 227 Event::unserialize(Checkpoint *cp, const string &section)
 228 {
 229     if (scheduled())
 230         mainEventQueue.deschedule(this);
 231
 232     UNSERIALIZE_SCALAR(_when);
 233     UNSERIALIZE_SCALAR(_priority);
 234
 235     // need to see if original event was in a scheduled, unsquashed
 236     // state, but don't want to restore those flags in the current
 237     // object itself (since they aren't immediately true)
 238     short _flags;
 239     UNSERIALIZE_SCALAR(_flags);
 240     flags = _flags;
 241
 242     bool wasScheduled = flags.isSet(Scheduled) && !flags.isSet(Squashed);
 243     flags.clear(Squashed | Scheduled);
 244
 245     if (wasScheduled) {
 246         DPRINTF(Config, "rescheduling at %d\n", _when);
 247         mainEventQueue.schedule(this, _when);
 248     }
 249 }
 250
 251 void
 252 EventQueue::serialize(ostream &os)
 253 {
 254     std::list<Event *> eventPtrs;
 255
 256     int numEvents = 0;
 257     Event *nextBin = head;
 258     while (nextBin) {
 259         Event *nextInBin = nextBin;
 260
 261         while (nextInBin) {
 262             if (nextInBin->flags.isSet(Event::AutoSerialize)) {
 263                 eventPtrs.push_back(nextInBin);
 264                 paramOut(os, csprintf("event%d", numEvents++),
 265                          nextInBin->name());
 266             }
 267             nextInBin = nextInBin->nextInBin;
 268         }
 269
 270         nextBin = nextBin->nextBin;
 271     }
 272
 273     SERIALIZE_SCALAR(numEvents);
 274
 275     for (std::list<Event *>::iterator it = eventPtrs.begin();
 276          it != eventPtrs.end(); ++it) {
 277         (*it)->nameOut(os);
 278         (*it)->serialize(os);
 279     }
 280 }
 281
 282 void
 283 EventQueue::unserialize(Checkpoint *cp, const std::string &section)
 284 {
 285     int numEvents;
 286     UNSERIALIZE_SCALAR(numEvents);
 287
 288     std::string eventName;
 289     for (int i = 0; i < numEvents; i++) {
 290         // get the pointer value associated with the event
 291         paramIn(cp, section, csprintf("event%d", i), eventName);
 292
 293         // create the event based on its pointer value
 294         Serializable::create(cp, eventName);
 295     }
 296 }
 297
 298 void
 299 EventQueue::dump() const
 300 {
 301     cprintf("============================================================\n");
 302     cprintf("EventQueue Dump  (cycle %d)\n", curTick);
 303     cprintf("------------------------------------------------------------\n");
 304
 305     if (empty())
 306         cprintf("<No Events>\n");
 307     else {
 308         Event *nextBin = head;
 309         while (nextBin) {
 310             Event *nextInBin = nextBin;
 311             while (nextInBin) {
 312                 nextInBin->dump();
 313                 nextInBin = nextInBin->nextInBin;
 314             }
 315
 316             nextBin = nextBin->nextBin;
 317         }
 318     }
 319
 320     cprintf("============================================================\n");
 321 }
 322
 323 bool
 324 EventQueue::debugVerify() const
 325 {
 326     m5::hash_map<long, bool> map;
 327
 328     Tick time = 0;
 329     short priority = 0;
 330
 331     Event *nextBin = head;
 332     while (nextBin) {
 333         Event *nextInBin = nextBin;
 334         while (nextInBin) {
 335             if (nextInBin->when() < time) {
 336                 cprintf("time goes backwards!");
 337                 nextInBin->dump();
 338                 return false;
 339             } else if (nextInBin->when() == time &&
 340                        nextInBin->priority() < priority) {
 341                 cprintf("priority inverted!");
 342                 nextInBin->dump();
 343                 return false;
 344             }
 345
 346             if (map[reinterpret_cast<long>(nextInBin)]) {
 347                 cprintf("Node already seen");
 348                 nextInBin->dump();
 349                 return false;
 350             }
 351             map[reinterpret_cast<long>(nextInBin)] = true;
 352
 353             time = nextInBin->when();
 354             priority = nextInBin->priority();
 355
 356             nextInBin = nextInBin->nextInBin;
 357         }
 358
 359         nextBin = nextBin->nextBin;
 360     }
 361
 362     return true;
 363 }
 364
 365 void
 366 dumpMainQueue()
 367 {
 368     mainEventQueue.dump();
 369 }
 370
 371
 372 const char *
 373 Event::description() const
 374 {
 375     return "generic";
 376 }
 377
 378 void
 379 Event::trace(const char *action)
 380 {
 381     // This DPRINTF is unconditional because calls to this function
 382     // are protected by an 'if (DTRACE(Event))' in the inlined Event
 383     // methods.
 384     //
 385     // This is just a default implementation for derived classes where
 386     // it's not worth doing anything special.  If you want to put a
 387     // more informative message in the trace, override this method on
 388     // the particular subclass where you have the information that
 389     // needs to be printed.
 390     DPRINTFN("%s event %s @ %d\n", description(), action, when());
 391 }
 392
 393 void
 394 Event::dump() const
 395 {
 396     cprintf("Event %s (%s)\n", name(), description());
 397     cprintf("Flags: %#x\n", flags);
 398 #ifdef EVENTQ_DEBUG
 399     cprintf("Created: %d\n", whenCreated);
 400 #endif
 401     if (scheduled()) {
 402 #ifdef EVENTQ_DEBUG
 403         cprintf("Scheduled at  %d\n", whenScheduled);
 404 #endif
 405         cprintf("Scheduled for %d, priority %d\n", when(), _priority);
 406     } else {
 407         cprintf("Not Scheduled\n");
 408     }
 409 }