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