eventq.cc revision 5695
12SN/A/*
21762SN/A * Copyright (c) 2000-2005 The Regents of The University of Michigan
35502Snate@binkert.org * Copyright (c) 2008 The Hewlett-Packard Development Company
42SN/A * All rights reserved.
52SN/A *
62SN/A * Redistribution and use in source and binary forms, with or without
72SN/A * modification, are permitted provided that the following conditions are
82SN/A * met: redistributions of source code must retain the above copyright
92SN/A * notice, this list of conditions and the following disclaimer;
102SN/A * redistributions in binary form must reproduce the above copyright
112SN/A * notice, this list of conditions and the following disclaimer in the
122SN/A * documentation and/or other materials provided with the distribution;
132SN/A * neither the name of the copyright holders nor the names of its
142SN/A * contributors may be used to endorse or promote products derived from
152SN/A * this software without specific prior written permission.
162SN/A *
172SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
182SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
192SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
202SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
212SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
222SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
232SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
242SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
252SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
262SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
272SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
282665Ssaidi@eecs.umich.edu *
292665Ssaidi@eecs.umich.edu * Authors: Steve Reinhardt
302665Ssaidi@eecs.umich.edu *          Nathan Binkert
312665Ssaidi@eecs.umich.edu *          Steve Raasch
322SN/A */
332SN/A
345501Snate@binkert.org#include <cassert>
352SN/A#include <iostream>
362SN/A#include <string>
372SN/A#include <vector>
382SN/A
395502Snate@binkert.org#include "base/hashmap.hh"
405501Snate@binkert.org#include "base/misc.hh"
415501Snate@binkert.org#include "base/trace.hh"
421717SN/A#include "cpu/smt.hh"
435501Snate@binkert.org#include "sim/core.hh"
4456SN/A#include "sim/eventq.hh"
452SN/A
462SN/Ausing namespace std;
472SN/A
482SN/A//
492SN/A// Main Event Queue
502SN/A//
512SN/A// Events on this queue are processed at the *beginning* of each
522SN/A// cycle, before the pipeline simulation is performed.
532SN/A//
545605Snate@binkert.orgEventQueue mainEventQueue("Main Event Queue");
552SN/A
564017Sstever@eecs.umich.edu#ifndef NDEBUG
574016Sstever@eecs.umich.eduCounter Event::instanceCounter = 0;
584017Sstever@eecs.umich.edu#endif
594016Sstever@eecs.umich.edu
605602Snate@binkert.orgEvent *
615602Snate@binkert.orgEvent::insertBefore(Event *event, Event *curr)
625502Snate@binkert.org{
635503Snate@binkert.org    // Either way, event will be the top element in the 'in bin' list
645502Snate@binkert.org    // which is the pointer we need in order to look into the list, so
655502Snate@binkert.org    // we need to insert that into the bin list.
665502Snate@binkert.org    if (!curr || *event < *curr) {
675502Snate@binkert.org        // Insert the event before the current list since it is in the future.
685502Snate@binkert.org        event->nextBin = curr;
695503Snate@binkert.org        event->nextInBin = NULL;
705502Snate@binkert.org    } else {
715502Snate@binkert.org        // Since we're on the correct list, we need to point to the next list
725502Snate@binkert.org        event->nextBin = curr->nextBin;  // curr->nextBin can now become stale
735502Snate@binkert.org
745503Snate@binkert.org        // Insert event at the top of the stack
755503Snate@binkert.org        event->nextInBin = curr;
765503Snate@binkert.org    }
775502Snate@binkert.org
785503Snate@binkert.org    return event;
795502Snate@binkert.org}
805502Snate@binkert.org
812SN/Avoid
822SN/AEventQueue::insert(Event *event)
832SN/A{
845502Snate@binkert.org    // Deal with the head case
855502Snate@binkert.org    if (!head || *event <= *head) {
865602Snate@binkert.org        head = Event::insertBefore(event, head);
875502Snate@binkert.org        return;
885502Snate@binkert.org    }
892SN/A
905502Snate@binkert.org    // Figure out either which 'in bin' list we are on, or where a new list
915502Snate@binkert.org    // needs to be inserted
925503Snate@binkert.org    Event *prev = head;
935503Snate@binkert.org    Event *curr = head->nextBin;
945503Snate@binkert.org    while (curr && *curr < *event) {
955503Snate@binkert.org        prev = curr;
965503Snate@binkert.org        curr = curr->nextBin;
975502Snate@binkert.org    }
982SN/A
995503Snate@binkert.org    // Note: this operation may render all nextBin pointers on the
1005503Snate@binkert.org    // prev 'in bin' list stale (except for the top one)
1015602Snate@binkert.org    prev->nextBin = Event::insertBefore(event, curr);
1025502Snate@binkert.org}
1032SN/A
1045602Snate@binkert.orgEvent *
1055602Snate@binkert.orgEvent::removeItem(Event *event, Event *top)
1065502Snate@binkert.org{
1075503Snate@binkert.org    Event *curr = top;
1085503Snate@binkert.org    Event *next = top->nextInBin;
1095502Snate@binkert.org
1105503Snate@binkert.org    // if we removed the top item, we need to handle things specially
1115503Snate@binkert.org    // and just remove the top item, fixing up the next bin pointer of
1125503Snate@binkert.org    // the new top item
1135503Snate@binkert.org    if (event == top) {
1145503Snate@binkert.org        if (!next)
1155503Snate@binkert.org            return top->nextBin;
1165503Snate@binkert.org        next->nextBin = top->nextBin;
1175503Snate@binkert.org        return next;
1185503Snate@binkert.org    }
1195503Snate@binkert.org
1205503Snate@binkert.org    // Since we already checked the current element, we're going to
1215503Snate@binkert.org    // keep checking event against the next element.
1225503Snate@binkert.org    while (event != next) {
1235503Snate@binkert.org        if (!next)
1245502Snate@binkert.org            panic("event not found!");
1255502Snate@binkert.org
1265503Snate@binkert.org        curr = next;
1275503Snate@binkert.org        next = next->nextInBin;
1282SN/A    }
1295502Snate@binkert.org
1305503Snate@binkert.org    // remove next from the 'in bin' list since it's what we're looking for
1315503Snate@binkert.org    curr->nextInBin = next->nextInBin;
1325503Snate@binkert.org    return top;
1332SN/A}
1342SN/A
1352SN/Avoid
1362SN/AEventQueue::remove(Event *event)
1372SN/A{
1382SN/A    if (head == NULL)
1395502Snate@binkert.org        panic("event not found!");
1402SN/A
1415502Snate@binkert.org    // deal with an event on the head's 'in bin' list (event has the same
1425502Snate@binkert.org    // time as the head)
1435502Snate@binkert.org    if (*head == *event) {
1445602Snate@binkert.org        head = Event::removeItem(event, head);
1452SN/A        return;
1462SN/A    }
1472SN/A
1485502Snate@binkert.org    // Find the 'in bin' list that this event belongs on
1492SN/A    Event *prev = head;
1505502Snate@binkert.org    Event *curr = head->nextBin;
1515502Snate@binkert.org    while (curr && *curr < *event) {
1522SN/A        prev = curr;
1535502Snate@binkert.org        curr = curr->nextBin;
1542SN/A    }
1552SN/A
1565502Snate@binkert.org    if (!curr || *curr != *event)
1575502Snate@binkert.org        panic("event not found!");
1585502Snate@binkert.org
1595503Snate@binkert.org    // curr points to the top item of the the correct 'in bin' list, when
1605503Snate@binkert.org    // we remove an item, it returns the new top item (which may be
1615502Snate@binkert.org    // unchanged)
1625602Snate@binkert.org    prev->nextBin = Event::removeItem(event, curr);
1632SN/A}
1642SN/A
1652667Sstever@eecs.umich.eduEvent *
1662SN/AEventQueue::serviceOne()
1672SN/A{
1685503Snate@binkert.org    Event *event = head;
1695503Snate@binkert.org    Event *next = head->nextInBin;
1702SN/A    event->clearFlags(Event::Scheduled);
1715502Snate@binkert.org
1725503Snate@binkert.org    if (next) {
1735503Snate@binkert.org        // update the next bin pointer since it could be stale
1745503Snate@binkert.org        next->nextBin = head->nextBin;
1755503Snate@binkert.org
1765503Snate@binkert.org        // pop the stack
1775503Snate@binkert.org        head = next;
1785503Snate@binkert.org    } else {
1795502Snate@binkert.org        // this was the only element on the 'in bin' list, so get rid of
1805502Snate@binkert.org        // the 'in bin' list and point to the next bin list
1815503Snate@binkert.org        head = head->nextBin;
1825502Snate@binkert.org    }
1832SN/A
1842SN/A    // handle action
1852667Sstever@eecs.umich.edu    if (!event->squashed()) {
1862SN/A        event->process();
1872667Sstever@eecs.umich.edu        if (event->isExitEvent()) {
1882667Sstever@eecs.umich.edu            assert(!event->getFlags(Event::AutoDelete)); // would be silly
1892667Sstever@eecs.umich.edu            return event;
1902667Sstever@eecs.umich.edu        }
1912667Sstever@eecs.umich.edu    } else {
1922SN/A        event->clearFlags(Event::Squashed);
1932667Sstever@eecs.umich.edu    }
1942SN/A
195294SN/A    if (event->getFlags(Event::AutoDelete) && !event->scheduled())
1962SN/A        delete event;
1972667Sstever@eecs.umich.edu
1982667Sstever@eecs.umich.edu    return NULL;
1992SN/A}
2002SN/A
201224SN/Avoid
202224SN/AEvent::serialize(std::ostream &os)
203224SN/A{
204224SN/A    SERIALIZE_SCALAR(_when);
205224SN/A    SERIALIZE_SCALAR(_priority);
206224SN/A    SERIALIZE_ENUM(_flags);
207224SN/A}
208224SN/A
209224SN/Avoid
210237SN/AEvent::unserialize(Checkpoint *cp, const string &section)
211224SN/A{
2125695Snate@binkert.org    if (scheduled())
2135695Snate@binkert.org        mainEventQueue.deschedule(this);
214224SN/A
215224SN/A    UNSERIALIZE_SCALAR(_when);
216224SN/A    UNSERIALIZE_SCALAR(_priority);
217224SN/A
218224SN/A    // need to see if original event was in a scheduled, unsquashed
219224SN/A    // state, but don't want to restore those flags in the current
220224SN/A    // object itself (since they aren't immediately true)
221224SN/A    UNSERIALIZE_ENUM(_flags);
222224SN/A    bool wasScheduled = (_flags & Scheduled) && !(_flags & Squashed);
223224SN/A    _flags &= ~(Squashed | Scheduled);
224224SN/A
225224SN/A    if (wasScheduled) {
226224SN/A        DPRINTF(Config, "rescheduling at %d\n", _when);
2275695Snate@binkert.org        mainEventQueue.schedule(this, _when);
228224SN/A    }
229224SN/A}
230224SN/A
2312SN/Avoid
232217SN/AEventQueue::serialize(ostream &os)
2332SN/A{
234265SN/A    std::list<Event *> eventPtrs;
235237SN/A
236237SN/A    int numEvents = 0;
2375502Snate@binkert.org    Event *nextBin = head;
2385502Snate@binkert.org    while (nextBin) {
2395503Snate@binkert.org        Event *nextInBin = nextBin;
2405502Snate@binkert.org
2415503Snate@binkert.org        while (nextInBin) {
2425502Snate@binkert.org            if (nextInBin->getFlags(Event::AutoSerialize)) {
2435502Snate@binkert.org                eventPtrs.push_back(nextInBin);
2445502Snate@binkert.org                paramOut(os, csprintf("event%d", numEvents++),
2455502Snate@binkert.org                         nextInBin->name());
2465502Snate@binkert.org            }
2475502Snate@binkert.org            nextInBin = nextInBin->nextInBin;
2485503Snate@binkert.org        }
2495502Snate@binkert.org
2505502Snate@binkert.org        nextBin = nextBin->nextBin;
2512SN/A    }
252237SN/A
253265SN/A    SERIALIZE_SCALAR(numEvents);
254265SN/A
2555502Snate@binkert.org    for (std::list<Event *>::iterator it = eventPtrs.begin();
256265SN/A         it != eventPtrs.end(); ++it) {
257265SN/A        (*it)->nameOut(os);
258265SN/A        (*it)->serialize(os);
259265SN/A    }
2602SN/A}
2612SN/A
262237SN/Avoid
263237SN/AEventQueue::unserialize(Checkpoint *cp, const std::string &section)
264237SN/A{
265265SN/A    int numEvents;
266265SN/A    UNSERIALIZE_SCALAR(numEvents);
267265SN/A
268270SN/A    std::string eventName;
269265SN/A    for (int i = 0; i < numEvents; i++) {
270265SN/A        // get the pointer value associated with the event
271270SN/A        paramIn(cp, section, csprintf("event%d", i), eventName);
272265SN/A
273265SN/A        // create the event based on its pointer value
274395SN/A        Serializable::create(cp, eventName);
275237SN/A    }
276237SN/A}
277237SN/A
2782SN/Avoid
2795501Snate@binkert.orgEventQueue::dump() const
2802SN/A{
2812SN/A    cprintf("============================================================\n");
2822SN/A    cprintf("EventQueue Dump  (cycle %d)\n", curTick);
2832SN/A    cprintf("------------------------------------------------------------\n");
2842SN/A
2852SN/A    if (empty())
2862SN/A        cprintf("<No Events>\n");
2872SN/A    else {
2885502Snate@binkert.org        Event *nextBin = head;
2895502Snate@binkert.org        while (nextBin) {
2905502Snate@binkert.org            Event *nextInBin = nextBin;
2915503Snate@binkert.org            while (nextInBin) {
2925503Snate@binkert.org                nextInBin->dump();
2935502Snate@binkert.org                nextInBin = nextInBin->nextInBin;
2945503Snate@binkert.org            }
2955502Snate@binkert.org
2965502Snate@binkert.org            nextBin = nextBin->nextBin;
2972SN/A        }
2982SN/A    }
2992SN/A
3002SN/A    cprintf("============================================================\n");
3012SN/A}
3022SN/A
3035502Snate@binkert.orgbool
3045502Snate@binkert.orgEventQueue::debugVerify() const
3055502Snate@binkert.org{
3065502Snate@binkert.org    m5::hash_map<long, bool> map;
3075502Snate@binkert.org
3085502Snate@binkert.org    Tick time = 0;
3095502Snate@binkert.org    short priority = 0;
3105502Snate@binkert.org
3115502Snate@binkert.org    Event *nextBin = head;
3125502Snate@binkert.org    while (nextBin) {
3135503Snate@binkert.org        Event *nextInBin = nextBin;
3145503Snate@binkert.org        while (nextInBin) {
3155502Snate@binkert.org            if (nextInBin->when() < time) {
3165502Snate@binkert.org                cprintf("time goes backwards!");
3175502Snate@binkert.org                nextInBin->dump();
3185502Snate@binkert.org                return false;
3195502Snate@binkert.org            } else if (nextInBin->when() == time &&
3205502Snate@binkert.org                       nextInBin->priority() < priority) {
3215502Snate@binkert.org                cprintf("priority inverted!");
3225502Snate@binkert.org                nextInBin->dump();
3235502Snate@binkert.org                return false;
3245502Snate@binkert.org            }
3255502Snate@binkert.org
3265502Snate@binkert.org            if (map[reinterpret_cast<long>(nextInBin)]) {
3275502Snate@binkert.org                cprintf("Node already seen");
3285502Snate@binkert.org                nextInBin->dump();
3295502Snate@binkert.org                return false;
3305502Snate@binkert.org            }
3315502Snate@binkert.org            map[reinterpret_cast<long>(nextInBin)] = true;
3325502Snate@binkert.org
3335502Snate@binkert.org            time = nextInBin->when();
3345502Snate@binkert.org            priority = nextInBin->priority();
3355502Snate@binkert.org
3365502Snate@binkert.org            nextInBin = nextInBin->nextInBin;
3375503Snate@binkert.org        }
3385502Snate@binkert.org
3395502Snate@binkert.org        nextBin = nextBin->nextBin;
3405502Snate@binkert.org    }
3415502Snate@binkert.org
3425502Snate@binkert.org    return true;
3435502Snate@binkert.org}
3445502Snate@binkert.org
3451019SN/Avoid
3461019SN/AdumpMainQueue()
3471019SN/A{
3481019SN/A    mainEventQueue.dump();
3491019SN/A}
3501019SN/A
3512SN/A
3522SN/Aconst char *
3535336Shines@cs.fsu.eduEvent::description() const
3542SN/A{
3552SN/A    return "generic";
3562SN/A}
3572SN/A
3582SN/Avoid
3592SN/AEvent::trace(const char *action)
3602SN/A{
3612SN/A    // This DPRINTF is unconditional because calls to this function
3622SN/A    // are protected by an 'if (DTRACE(Event))' in the inlined Event
3632SN/A    // methods.
3642SN/A    //
3652SN/A    // This is just a default implementation for derived classes where
3662SN/A    // it's not worth doing anything special.  If you want to put a
3672SN/A    // more informative message in the trace, override this method on
3682SN/A    // the particular subclass where you have the information that
3692SN/A    // needs to be printed.
3702SN/A    DPRINTFN("%s event %s @ %d\n", description(), action, when());
3712SN/A}
3722SN/A
3732SN/Avoid
3745501Snate@binkert.orgEvent::dump() const
3752SN/A{
3765501Snate@binkert.org    cprintf("Event %s (%s)\n", name(), description());
3771019SN/A    cprintf("Flags: %#x\n", _flags);
3785501Snate@binkert.org#ifdef EVENTQ_DEBUG
3795501Snate@binkert.org    cprintf("Created: %d\n", whenCreated);
3802SN/A#endif
3812SN/A    if (scheduled()) {
3825501Snate@binkert.org#ifdef EVENTQ_DEBUG
3835501Snate@binkert.org        cprintf("Scheduled at  %d\n", whenScheduled);
3842SN/A#endif
3851019SN/A        cprintf("Scheduled for %d, priority %d\n", when(), _priority);
3865501Snate@binkert.org    } else {
3871019SN/A        cprintf("Not Scheduled\n");
3882SN/A    }
3892SN/A}
390