eventq.cc revision 5774
172SN/A/* 213575Sciro.santilli@arm.com * Copyright (c) 2000-2005 The Regents of The University of Michigan 313575Sciro.santilli@arm.com * Copyright (c) 2008 The Hewlett-Packard Development Company 413575Sciro.santilli@arm.com * All rights reserved. 513575Sciro.santilli@arm.com * 613575Sciro.santilli@arm.com * Redistribution and use in source and binary forms, with or without 713575Sciro.santilli@arm.com * modification, are permitted provided that the following conditions are 813575Sciro.santilli@arm.com * met: redistributions of source code must retain the above copyright 913575Sciro.santilli@arm.com * notice, this list of conditions and the following disclaimer; 1013575Sciro.santilli@arm.com * redistributions in binary form must reproduce the above copyright 1113575Sciro.santilli@arm.com * notice, this list of conditions and the following disclaimer in the 1213575Sciro.santilli@arm.com * documentation and/or other materials provided with the distribution; 1311274Sshingarov@labware.com * neither the name of the copyright holders nor the names of its 1410597Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 151762SN/A * this software without specific prior written permission. 1672SN/A * 1772SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1872SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1972SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2072SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2172SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2272SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2372SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2472SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2572SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2672SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2772SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2872SN/A * 2972SN/A * Authors: Steve Reinhardt 3072SN/A * Nathan Binkert 3172SN/A * Steve Raasch 3272SN/A */ 3372SN/A 3472SN/A#include <cassert> 3572SN/A#include <iostream> 3672SN/A#include <string> 3772SN/A#include <vector> 3872SN/A 3972SN/A#include "base/hashmap.hh" 402665Ssaidi@eecs.umich.edu#include "base/misc.hh" 412665Ssaidi@eecs.umich.edu#include "base/trace.hh" 4211274Sshingarov@labware.com#include "cpu/smt.hh" 4372SN/A#include "sim/core.hh" 4472SN/A#include "sim/eventq.hh" 452SN/A 468332Snate@binkert.orgusing namespace std; 478332Snate@binkert.org 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// 542SN/AEventQueue mainEventQueue("Main Event Queue"); 555543Ssaidi@eecs.umich.edu 565543Ssaidi@eecs.umich.edu#ifndef NDEBUG 572SN/ACounter Event::instanceCounter = 0; 582SN/A#endif 592SN/A 602SN/AEvent::~Event() 612SN/A{ 622SN/A assert(!scheduled()); 632SN/A} 642SN/A 652SN/Aconst std::string 662SN/AEvent::name() const 672SN/A{ 685543Ssaidi@eecs.umich.edu#ifndef NDEBUG 695543Ssaidi@eecs.umich.edu return csprintf("Event_%d", instance); 702SN/A#else 712SN/A return csprintf("Event_%x", (uintptr_t)this); 722SN/A#endif 732SN/A} 742SN/A 752SN/A 762SN/AEvent * 772SN/AEvent::insertBefore(Event *event, Event *curr) 782SN/A{ 792SN/A // Either way, event will be the top element in the 'in bin' list 802SN/A // which is the pointer we need in order to look into the list, so 812SN/A // we need to insert that into the bin list. 822SN/A if (!curr || *event < *curr) { 832SN/A // Insert the event before the current list since it is in the future. 842SN/A event->nextBin = curr; 852SN/A event->nextInBin = NULL; 865543Ssaidi@eecs.umich.edu } else { 872SN/A // Since we're on the correct list, we need to point to the next list 882SN/A event->nextBin = curr->nextBin; // curr->nextBin can now become stale 892SN/A 902SN/A // Insert event at the top of the stack 912SN/A event->nextInBin = curr; 922SN/A } 932SN/A 942SN/A return event; 952SN/A} 962SN/A 972SN/Avoid 982SN/AEventQueue::insert(Event *event) 992SN/A{ 1002SN/A // Deal with the head case 1012SN/A if (!head || *event <= *head) { 1022SN/A head = Event::insertBefore(event, head); 1032SN/A return; 1042SN/A } 1052SN/A 1065543Ssaidi@eecs.umich.edu // Figure out either which 'in bin' list we are on, or where a new list 1075543Ssaidi@eecs.umich.edu // needs to be inserted 1082SN/A Event *prev = head; 1092SN/A Event *curr = head->nextBin; 1102SN/A while (curr && *curr < *event) { 1112SN/A prev = curr; 1122SN/A curr = curr->nextBin; 1132SN/A } 1142SN/A 1152SN/A // Note: this operation may render all nextBin pointers on the 1162SN/A // prev 'in bin' list stale (except for the top one) 1172SN/A prev->nextBin = Event::insertBefore(event, curr); 1182SN/A} 1192SN/A 1202SN/AEvent * 1212SN/AEvent::removeItem(Event *event, Event *top) 1222SN/A{ 1232SN/A Event *curr = top; 1242SN/A Event *next = top->nextInBin; 1252SN/A 1262SN/A // if we removed the top item, we need to handle things specially 1272SN/A // and just remove the top item, fixing up the next bin pointer of 1282SN/A // the new top item 1292SN/A if (event == top) { 1302SN/A if (!next) 1312SN/A return top->nextBin; 1322SN/A next->nextBin = top->nextBin; 13311793Sbrandon.potter@amd.com return next; 13411793Sbrandon.potter@amd.com } 1352SN/A 1368229Snate@binkert.org // Since we already checked the current element, we're going to 1372SN/A // keep checking event against the next element. 13811793Sbrandon.potter@amd.com while (event != next) { 13912019Sgabeblack@google.com if (!next) 1406712Snate@binkert.org panic("event not found!"); 14113575Sciro.santilli@arm.com 1421717SN/A curr = next; 1432SN/A next = next->nextInBin; 1442521SN/A } 14556SN/A 14656SN/A // remove next from the 'in bin' list since it's what we're looking for 14756SN/A curr->nextInBin = next->nextInBin; 1486658Snate@binkert.org return top; 14910597Sgabeblack@google.com} 1508229Snate@binkert.org 1512680Sktlim@umich.eduvoid 1528232Snate@binkert.orgEventQueue::remove(Event *event) 15311793Sbrandon.potter@amd.com{ 1542521SN/A if (head == NULL) 1558706Sandreas.hansson@arm.com panic("event not found!"); 1568784Sgblack@eecs.umich.edu 1571717SN/A // deal with an event on the head's 'in bin' list (event has the same 1582SN/A // time as the head) 1592SN/A if (*head == *event) { 1602107SN/A head = Event::removeItem(event, head); 1612SN/A return; 16212031Sgabeblack@google.com } 16312031Sgabeblack@google.com 16412031Sgabeblack@google.com // Find the 'in bin' list that this event belongs on 16512031Sgabeblack@google.com Event *prev = head; 16612031Sgabeblack@google.com Event *curr = head->nextBin; 1673536Sgblack@eecs.umich.edu while (curr && *curr < *event) { 1682SN/A prev = curr; 16912449Sgabeblack@google.com curr = curr->nextBin; 17012449Sgabeblack@google.com } 17112449Sgabeblack@google.com 17212449Sgabeblack@google.com if (!curr || *curr != *event) 17312449Sgabeblack@google.com panic("event not found!"); 17412449Sgabeblack@google.com 17512449Sgabeblack@google.com // curr points to the top item of the the correct 'in bin' list, when 17612449Sgabeblack@google.com // we remove an item, it returns the new top item (which may be 17712449Sgabeblack@google.com // unchanged) 17812449Sgabeblack@google.com prev->nextBin = Event::removeItem(event, curr); 17912449Sgabeblack@google.com} 18012449Sgabeblack@google.com 18112449Sgabeblack@google.comEvent * 18212449Sgabeblack@google.comEventQueue::serviceOne() 18312449Sgabeblack@google.com{ 18412449Sgabeblack@google.com Event *event = head; 18512466Sgabeblack@google.com Event *next = head->nextInBin; 18612449Sgabeblack@google.com event->flags.clear(Event::Scheduled); 18712449Sgabeblack@google.com 18812449Sgabeblack@google.com if (next) { 18912449Sgabeblack@google.com // update the next bin pointer since it could be stale 19012449Sgabeblack@google.com next->nextBin = head->nextBin; 19112449Sgabeblack@google.com 19212449Sgabeblack@google.com // pop the stack 19312449Sgabeblack@google.com head = next; 19412449Sgabeblack@google.com } else { 19512449Sgabeblack@google.com // this was the only element on the 'in bin' list, so get rid of 19612449Sgabeblack@google.com // the 'in bin' list and point to the next bin list 19712449Sgabeblack@google.com head = head->nextBin; 19812449Sgabeblack@google.com } 19912449Sgabeblack@google.com 20012449Sgabeblack@google.com // handle action 20112449Sgabeblack@google.com if (!event->squashed()) { 20212449Sgabeblack@google.com event->process(); 20312449Sgabeblack@google.com if (event->isExitEvent()) { 20412449Sgabeblack@google.com assert(!event->flags.isSet(Event::AutoDelete)); // would be silly 20512449Sgabeblack@google.com return event; 20612449Sgabeblack@google.com } 20712449Sgabeblack@google.com } else { 20812449Sgabeblack@google.com event->flags.clear(Event::Squashed); 20912449Sgabeblack@google.com } 21012449Sgabeblack@google.com 21112449Sgabeblack@google.com if (event->flags.isSet(Event::AutoDelete) && !event->scheduled()) 21212449Sgabeblack@google.com delete event; 21312449Sgabeblack@google.com 21412449Sgabeblack@google.com return NULL; 21512449Sgabeblack@google.com} 21612449Sgabeblack@google.com 21712449Sgabeblack@google.comvoid 21812449Sgabeblack@google.comEvent::serialize(std::ostream &os) 21912449Sgabeblack@google.com{ 22012449Sgabeblack@google.com SERIALIZE_SCALAR(_when); 22112449Sgabeblack@google.com SERIALIZE_SCALAR(_priority); 22212449Sgabeblack@google.com short _flags = flags; 22312449Sgabeblack@google.com SERIALIZE_SCALAR(_flags); 22412449Sgabeblack@google.com} 22512449Sgabeblack@google.com 22612449Sgabeblack@google.comvoid 22712449Sgabeblack@google.comEvent::unserialize(Checkpoint *cp, const string §ion) 22812449Sgabeblack@google.com{ 22912449Sgabeblack@google.com if (scheduled()) 23012449Sgabeblack@google.com mainEventQueue.deschedule(this); 23112449Sgabeblack@google.com 23212449Sgabeblack@google.com UNSERIALIZE_SCALAR(_when); 23312449Sgabeblack@google.com UNSERIALIZE_SCALAR(_priority); 23412449Sgabeblack@google.com 23512449Sgabeblack@google.com // need to see if original event was in a scheduled, unsquashed 23612449Sgabeblack@google.com // state, but don't want to restore those flags in the current 23712449Sgabeblack@google.com // object itself (since they aren't immediately true) 23812449Sgabeblack@google.com short _flags; 23912449Sgabeblack@google.com UNSERIALIZE_SCALAR(_flags); 24012449Sgabeblack@google.com flags = _flags; 2412SN/A 24212449Sgabeblack@google.com bool wasScheduled = flags.isSet(Scheduled) && !flags.isSet(Squashed); 2432SN/A flags.clear(Squashed | Scheduled); 24412449Sgabeblack@google.com 24512449Sgabeblack@google.com if (wasScheduled) { 24612449Sgabeblack@google.com DPRINTF(Config, "rescheduling at %d\n", _when); 24712449Sgabeblack@google.com mainEventQueue.schedule(this, _when); 24812449Sgabeblack@google.com } 24912449Sgabeblack@google.com} 25012449Sgabeblack@google.com 25112449Sgabeblack@google.comvoid 25212449Sgabeblack@google.comEventQueue::serialize(ostream &os) 25312449Sgabeblack@google.com{ 25412449Sgabeblack@google.com std::list<Event *> eventPtrs; 25512449Sgabeblack@google.com 25612449Sgabeblack@google.com int numEvents = 0; 25712449Sgabeblack@google.com Event *nextBin = head; 25812449Sgabeblack@google.com while (nextBin) { 25912449Sgabeblack@google.com Event *nextInBin = nextBin; 26012449Sgabeblack@google.com 26112449Sgabeblack@google.com while (nextInBin) { 26212449Sgabeblack@google.com if (nextInBin->flags.isSet(Event::AutoSerialize)) { 26312449Sgabeblack@google.com eventPtrs.push_back(nextInBin); 26412449Sgabeblack@google.com paramOut(os, csprintf("event%d", numEvents++), 26512449Sgabeblack@google.com nextInBin->name()); 26612449Sgabeblack@google.com } 26712449Sgabeblack@google.com nextInBin = nextInBin->nextInBin; 26812449Sgabeblack@google.com } 26912449Sgabeblack@google.com 27012449Sgabeblack@google.com nextBin = nextBin->nextBin; 27112449Sgabeblack@google.com } 27212449Sgabeblack@google.com 27312449Sgabeblack@google.com SERIALIZE_SCALAR(numEvents); 27412449Sgabeblack@google.com 27512449Sgabeblack@google.com for (std::list<Event *>::iterator it = eventPtrs.begin(); 27612449Sgabeblack@google.com it != eventPtrs.end(); ++it) { 27712449Sgabeblack@google.com (*it)->nameOut(os); 27812449Sgabeblack@google.com (*it)->serialize(os); 27912449Sgabeblack@google.com } 28012449Sgabeblack@google.com} 28112449Sgabeblack@google.com 28212449Sgabeblack@google.comvoid 28312449Sgabeblack@google.comEventQueue::unserialize(Checkpoint *cp, const std::string §ion) 28412449Sgabeblack@google.com{ 28512449Sgabeblack@google.com int numEvents; 28612449Sgabeblack@google.com UNSERIALIZE_SCALAR(numEvents); 28712449Sgabeblack@google.com 28812449Sgabeblack@google.com std::string eventName; 28912449Sgabeblack@google.com for (int i = 0; i < numEvents; i++) { 29012449Sgabeblack@google.com // get the pointer value associated with the event 29112449Sgabeblack@google.com paramIn(cp, section, csprintf("event%d", i), eventName); 29212449Sgabeblack@google.com 29312449Sgabeblack@google.com // create the event based on its pointer value 29412449Sgabeblack@google.com Serializable::create(cp, eventName); 29512449Sgabeblack@google.com } 29612449Sgabeblack@google.com} 29712449Sgabeblack@google.com 29812449Sgabeblack@google.comvoid 29912449Sgabeblack@google.comEventQueue::dump() const 30012449Sgabeblack@google.com{ 30112449Sgabeblack@google.com cprintf("============================================================\n"); 30212449Sgabeblack@google.com cprintf("EventQueue Dump (cycle %d)\n", curTick); 30312487Snikos.nikoleris@arm.com cprintf("------------------------------------------------------------\n"); 30412449Sgabeblack@google.com 30512449Sgabeblack@google.com if (empty()) 30612449Sgabeblack@google.com cprintf("<No Events>\n"); 30712449Sgabeblack@google.com else { 30812449Sgabeblack@google.com Event *nextBin = head; 30912449Sgabeblack@google.com while (nextBin) { 31012449Sgabeblack@google.com Event *nextInBin = nextBin; 31112449Sgabeblack@google.com while (nextInBin) { 31212449Sgabeblack@google.com nextInBin->dump(); 31312449Sgabeblack@google.com nextInBin = nextInBin->nextInBin; 3141910SN/A } 3152SN/A 31612487Snikos.nikoleris@arm.com nextBin = nextBin->nextBin; 3172SN/A } 31812449Sgabeblack@google.com } 3192SN/A 32012449Sgabeblack@google.com cprintf("============================================================\n"); 32112449Sgabeblack@google.com} 3222SN/A 32312449Sgabeblack@google.combool 3242SN/AEventQueue::debugVerify() const 3252SN/A{ 3261910SN/A m5::hash_map<long, bool> map; 3272SN/A 32812449Sgabeblack@google.com Tick time = 0; 32912449Sgabeblack@google.com short priority = 0; 33012449Sgabeblack@google.com 33112449Sgabeblack@google.com Event *nextBin = head; 3322SN/A while (nextBin) { 33312449Sgabeblack@google.com Event *nextInBin = nextBin; 33412449Sgabeblack@google.com while (nextInBin) { 33512449Sgabeblack@google.com if (nextInBin->when() < time) { 33612449Sgabeblack@google.com cprintf("time goes backwards!"); 33712449Sgabeblack@google.com nextInBin->dump(); 33812449Sgabeblack@google.com return false; 33912449Sgabeblack@google.com } else if (nextInBin->when() == time && 3402SN/A nextInBin->priority() < priority) { 3412SN/A cprintf("priority inverted!"); 342507SN/A nextInBin->dump(); 34312449Sgabeblack@google.com return false; 344507SN/A } 34512449Sgabeblack@google.com 346507SN/A if (map[reinterpret_cast<long>(nextInBin)]) { 347507SN/A cprintf("Node already seen"); 3482SN/A nextInBin->dump(); 34912449Sgabeblack@google.com return false; 3502SN/A } 3515523Snate@binkert.org map[reinterpret_cast<long>(nextInBin)] = true; 3525523Snate@binkert.org 3535523Snate@binkert.org time = nextInBin->when(); 3545523Snate@binkert.org priority = nextInBin->priority(); 3555523Snate@binkert.org 35612449Sgabeblack@google.com nextInBin = nextInBin->nextInBin; 35712449Sgabeblack@google.com } 35812449Sgabeblack@google.com 3592SN/A nextBin = nextBin->nextBin; 3602SN/A } 36112449Sgabeblack@google.com 36212449Sgabeblack@google.com return true; 3631910SN/A} 3641910SN/A 36512449Sgabeblack@google.comvoid 3662SN/AdumpMainQueue() 3672SN/A{ 3682SN/A mainEventQueue.dump(); 36912449Sgabeblack@google.com} 3702SN/A 37112449Sgabeblack@google.com 37212449Sgabeblack@google.comconst char * 3732SN/AEvent::description() const 3742SN/A{ 3752SN/A return "generic"; 3762SN/A} 37712449Sgabeblack@google.com 3782SN/Avoid 3792SN/AEvent::trace(const char *action) 38012449Sgabeblack@google.com{ 3812SN/A // This DPRINTF is unconditional because calls to this function 3822SN/A // are protected by an 'if (DTRACE(Event))' in the inlined Event 3832SN/A // methods. 38412122Sjose.marinho@arm.com // 38512449Sgabeblack@google.com // This is just a default implementation for derived classes where 38612122Sjose.marinho@arm.com // it's not worth doing anything special. If you want to put a 38712122Sjose.marinho@arm.com // more informative message in the trace, override this method on 38812449Sgabeblack@google.com // the particular subclass where you have the information that 38912449Sgabeblack@google.com // needs to be printed. 39012122Sjose.marinho@arm.com DPRINTFN("%s event %s @ %d\n", description(), action, when()); 39112122Sjose.marinho@arm.com} 3922SN/A 3933536Sgblack@eecs.umich.eduvoid 3942SN/AEvent::dump() const 3952SN/A{ 3962SN/A cprintf("Event %s (%s)\n", name(), description()); 39712449Sgabeblack@google.com cprintf("Flags: %#x\n", flags); 39812449Sgabeblack@google.com#ifdef EVENTQ_DEBUG 3992SN/A cprintf("Created: %d\n", whenCreated); 4002SN/A#endif 4012SN/A if (scheduled()) { 4022SN/A#ifdef EVENTQ_DEBUG 4032SN/A cprintf("Scheduled at %d\n", whenScheduled); 4042SN/A#endif 4053536Sgblack@eecs.umich.edu cprintf("Scheduled for %d, priority %d\n", when(), _priority); 4062SN/A } else { 4072SN/A cprintf("Not Scheduled\n"); 40812031Sgabeblack@google.com } 40912031Sgabeblack@google.com} 4102SN/A