eventq.cc revision 11320
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 49983Sstever@gmail.com * Copyright (c) 2013 Advanced Micro Devices, Inc. 52SN/A * All rights reserved. 62SN/A * 72SN/A * Redistribution and use in source and binary forms, with or without 82SN/A * modification, are permitted provided that the following conditions are 92SN/A * met: redistributions of source code must retain the above copyright 102SN/A * notice, this list of conditions and the following disclaimer; 112SN/A * redistributions in binary form must reproduce the above copyright 122SN/A * notice, this list of conditions and the following disclaimer in the 132SN/A * documentation and/or other materials provided with the distribution; 142SN/A * neither the name of the copyright holders nor the names of its 152SN/A * contributors may be used to endorse or promote products derived from 162SN/A * this software without specific prior written permission. 172SN/A * 182SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 192SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 202SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 212SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 222SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 232SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 242SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 252SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 262SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 272SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 282SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 292665Ssaidi@eecs.umich.edu * 302665Ssaidi@eecs.umich.edu * Authors: Steve Reinhardt 312665Ssaidi@eecs.umich.edu * Nathan Binkert 322665Ssaidi@eecs.umich.edu * Steve Raasch 332SN/A */ 342SN/A 355501Snate@binkert.org#include <cassert> 362SN/A#include <iostream> 372SN/A#include <string> 3811168Sandreas.hansson@arm.com#include <unordered_map> 392SN/A#include <vector> 402SN/A 415501Snate@binkert.org#include "base/misc.hh" 425501Snate@binkert.org#include "base/trace.hh" 431717SN/A#include "cpu/smt.hh" 4410906Sandreas.sandberg@arm.com#include "debug/Checkpoint.hh" 455501Snate@binkert.org#include "sim/core.hh" 469356Snilay@cs.wisc.edu#include "sim/eventq_impl.hh" 472SN/A 482SN/Ausing namespace std; 492SN/A 509983Sstever@gmail.comTick simQuantum = 0; 519983Sstever@gmail.com 522SN/A// 539983Sstever@gmail.com// Main Event Queues 542SN/A// 559983Sstever@gmail.com// Events on these queues are processed at the *beginning* of each 562SN/A// cycle, before the pipeline simulation is performed. 572SN/A// 589983Sstever@gmail.comuint32_t numMainEventQueues = 0; 599983Sstever@gmail.comvector<EventQueue *> mainEventQueue; 609983Sstever@gmail.com__thread EventQueue *_curEventQueue = NULL; 619983Sstever@gmail.combool inParallelMode = false; 629983Sstever@gmail.com 639983Sstever@gmail.comEventQueue * 649983Sstever@gmail.comgetEventQueue(uint32_t index) 659983Sstever@gmail.com{ 669983Sstever@gmail.com while (numMainEventQueues <= index) { 679983Sstever@gmail.com numMainEventQueues++; 689983Sstever@gmail.com mainEventQueue.push_back( 699983Sstever@gmail.com new EventQueue(csprintf("MainEventQueue-%d", index))); 709983Sstever@gmail.com } 719983Sstever@gmail.com 729983Sstever@gmail.com return mainEventQueue[index]; 739983Sstever@gmail.com} 742SN/A 754017Sstever@eecs.umich.edu#ifndef NDEBUG 764016Sstever@eecs.umich.eduCounter Event::instanceCounter = 0; 774017Sstever@eecs.umich.edu#endif 784016Sstever@eecs.umich.edu 795768Snate@binkert.orgEvent::~Event() 805768Snate@binkert.org{ 815774Snate@binkert.org assert(!scheduled()); 827059Snate@binkert.org flags = 0; 835768Snate@binkert.org} 845768Snate@binkert.org 855768Snate@binkert.orgconst std::string 865768Snate@binkert.orgEvent::name() const 875768Snate@binkert.org{ 885768Snate@binkert.org#ifndef NDEBUG 895768Snate@binkert.org return csprintf("Event_%d", instance); 905768Snate@binkert.org#else 915768Snate@binkert.org return csprintf("Event_%x", (uintptr_t)this); 925768Snate@binkert.org#endif 935768Snate@binkert.org} 945768Snate@binkert.org 955768Snate@binkert.org 965602Snate@binkert.orgEvent * 975602Snate@binkert.orgEvent::insertBefore(Event *event, Event *curr) 985502Snate@binkert.org{ 995503Snate@binkert.org // Either way, event will be the top element in the 'in bin' list 1005502Snate@binkert.org // which is the pointer we need in order to look into the list, so 1015502Snate@binkert.org // we need to insert that into the bin list. 1025502Snate@binkert.org if (!curr || *event < *curr) { 1035502Snate@binkert.org // Insert the event before the current list since it is in the future. 1045502Snate@binkert.org event->nextBin = curr; 1055503Snate@binkert.org event->nextInBin = NULL; 1065502Snate@binkert.org } else { 1075502Snate@binkert.org // Since we're on the correct list, we need to point to the next list 1085502Snate@binkert.org event->nextBin = curr->nextBin; // curr->nextBin can now become stale 1095502Snate@binkert.org 1105503Snate@binkert.org // Insert event at the top of the stack 1115503Snate@binkert.org event->nextInBin = curr; 1125503Snate@binkert.org } 1135502Snate@binkert.org 1145503Snate@binkert.org return event; 1155502Snate@binkert.org} 1165502Snate@binkert.org 1172SN/Avoid 1182SN/AEventQueue::insert(Event *event) 1192SN/A{ 1205502Snate@binkert.org // Deal with the head case 1215502Snate@binkert.org if (!head || *event <= *head) { 1225602Snate@binkert.org head = Event::insertBefore(event, head); 1235502Snate@binkert.org return; 1245502Snate@binkert.org } 1252SN/A 1265502Snate@binkert.org // Figure out either which 'in bin' list we are on, or where a new list 1275502Snate@binkert.org // needs to be inserted 1285503Snate@binkert.org Event *prev = head; 1295503Snate@binkert.org Event *curr = head->nextBin; 1305503Snate@binkert.org while (curr && *curr < *event) { 1315503Snate@binkert.org prev = curr; 1325503Snate@binkert.org curr = curr->nextBin; 1335502Snate@binkert.org } 1342SN/A 1355503Snate@binkert.org // Note: this operation may render all nextBin pointers on the 1365503Snate@binkert.org // prev 'in bin' list stale (except for the top one) 1375602Snate@binkert.org prev->nextBin = Event::insertBefore(event, curr); 1385502Snate@binkert.org} 1392SN/A 1405602Snate@binkert.orgEvent * 1415602Snate@binkert.orgEvent::removeItem(Event *event, Event *top) 1425502Snate@binkert.org{ 1435503Snate@binkert.org Event *curr = top; 1445503Snate@binkert.org Event *next = top->nextInBin; 1455502Snate@binkert.org 1465503Snate@binkert.org // if we removed the top item, we need to handle things specially 1475503Snate@binkert.org // and just remove the top item, fixing up the next bin pointer of 1485503Snate@binkert.org // the new top item 1495503Snate@binkert.org if (event == top) { 1505503Snate@binkert.org if (!next) 1515503Snate@binkert.org return top->nextBin; 1525503Snate@binkert.org next->nextBin = top->nextBin; 1535503Snate@binkert.org return next; 1545503Snate@binkert.org } 1555503Snate@binkert.org 1565503Snate@binkert.org // Since we already checked the current element, we're going to 1575503Snate@binkert.org // keep checking event against the next element. 1585503Snate@binkert.org while (event != next) { 1595503Snate@binkert.org if (!next) 1605502Snate@binkert.org panic("event not found!"); 1615502Snate@binkert.org 1625503Snate@binkert.org curr = next; 1635503Snate@binkert.org next = next->nextInBin; 1642SN/A } 1655502Snate@binkert.org 1665503Snate@binkert.org // remove next from the 'in bin' list since it's what we're looking for 1675503Snate@binkert.org curr->nextInBin = next->nextInBin; 1685503Snate@binkert.org return top; 1692SN/A} 1702SN/A 1712SN/Avoid 1722SN/AEventQueue::remove(Event *event) 1732SN/A{ 1742SN/A if (head == NULL) 1755502Snate@binkert.org panic("event not found!"); 1762SN/A 1779983Sstever@gmail.com assert(event->queue == this); 1789983Sstever@gmail.com 1795502Snate@binkert.org // deal with an event on the head's 'in bin' list (event has the same 1805502Snate@binkert.org // time as the head) 1815502Snate@binkert.org if (*head == *event) { 1825602Snate@binkert.org head = Event::removeItem(event, head); 1832SN/A return; 1842SN/A } 1852SN/A 1865502Snate@binkert.org // Find the 'in bin' list that this event belongs on 1872SN/A Event *prev = head; 1885502Snate@binkert.org Event *curr = head->nextBin; 1895502Snate@binkert.org while (curr && *curr < *event) { 1902SN/A prev = curr; 1915502Snate@binkert.org curr = curr->nextBin; 1922SN/A } 1932SN/A 1945502Snate@binkert.org if (!curr || *curr != *event) 1955502Snate@binkert.org panic("event not found!"); 1965502Snate@binkert.org 1975503Snate@binkert.org // curr points to the top item of the the correct 'in bin' list, when 1985503Snate@binkert.org // we remove an item, it returns the new top item (which may be 1995502Snate@binkert.org // unchanged) 2005602Snate@binkert.org prev->nextBin = Event::removeItem(event, curr); 2012SN/A} 2022SN/A 2032667Sstever@eecs.umich.eduEvent * 2042SN/AEventQueue::serviceOne() 2052SN/A{ 20610153Sandreas@sandberg.pp.se std::lock_guard<EventQueue> lock(*this); 2075503Snate@binkert.org Event *event = head; 2085503Snate@binkert.org Event *next = head->nextInBin; 2095769Snate@binkert.org event->flags.clear(Event::Scheduled); 2105502Snate@binkert.org 2115503Snate@binkert.org if (next) { 2125503Snate@binkert.org // update the next bin pointer since it could be stale 2135503Snate@binkert.org next->nextBin = head->nextBin; 2145503Snate@binkert.org 2155503Snate@binkert.org // pop the stack 2165503Snate@binkert.org head = next; 2175503Snate@binkert.org } else { 2185502Snate@binkert.org // this was the only element on the 'in bin' list, so get rid of 2195502Snate@binkert.org // the 'in bin' list and point to the next bin list 2205503Snate@binkert.org head = head->nextBin; 2215502Snate@binkert.org } 2222SN/A 2232SN/A // handle action 2242667Sstever@eecs.umich.edu if (!event->squashed()) { 2259356Snilay@cs.wisc.edu // forward current cycle to the time when this event occurs. 2269356Snilay@cs.wisc.edu setCurTick(event->when()); 2279356Snilay@cs.wisc.edu 2282SN/A event->process(); 2292667Sstever@eecs.umich.edu if (event->isExitEvent()) { 2309328SAli.Saidi@ARM.com assert(!event->flags.isSet(Event::AutoDelete) || 2319328SAli.Saidi@ARM.com !event->flags.isSet(Event::IsMainQueue)); // would be silly 2322667Sstever@eecs.umich.edu return event; 2332667Sstever@eecs.umich.edu } 2342667Sstever@eecs.umich.edu } else { 2355769Snate@binkert.org event->flags.clear(Event::Squashed); 2362667Sstever@eecs.umich.edu } 2372SN/A 2385769Snate@binkert.org if (event->flags.isSet(Event::AutoDelete) && !event->scheduled()) 2392SN/A delete event; 2402667Sstever@eecs.umich.edu 2412667Sstever@eecs.umich.edu return NULL; 2422SN/A} 2432SN/A 244224SN/Avoid 24510905Sandreas.sandberg@arm.comEvent::serialize(CheckpointOut &cp) const 246224SN/A{ 247224SN/A SERIALIZE_SCALAR(_when); 248224SN/A SERIALIZE_SCALAR(_priority); 2495769Snate@binkert.org short _flags = flags; 2505769Snate@binkert.org SERIALIZE_SCALAR(_flags); 251224SN/A} 252224SN/A 253224SN/Avoid 25410905Sandreas.sandberg@arm.comEvent::unserialize(CheckpointIn &cp) 255224SN/A{ 25610906Sandreas.sandberg@arm.com assert(!scheduled()); 257224SN/A 258224SN/A UNSERIALIZE_SCALAR(_when); 259224SN/A UNSERIALIZE_SCALAR(_priority); 260224SN/A 26110906Sandreas.sandberg@arm.com FlagsType _flags; 2625769Snate@binkert.org UNSERIALIZE_SCALAR(_flags); 2637452SLisa.Hsu@amd.com 2647452SLisa.Hsu@amd.com // Old checkpoints had no concept of the Initialized flag 2657452SLisa.Hsu@amd.com // so restoring from old checkpoints always fail. 26611320Ssteve.reinhardt@amd.com // Events are initialized on construction but original code 26711320Ssteve.reinhardt@amd.com // "flags = _flags" would just overwrite the initialization. 26811320Ssteve.reinhardt@amd.com // So, read in the checkpoint flags, but then set the Initialized 2697452SLisa.Hsu@amd.com // flag on top of it in order to avoid failures. 2707451SLisa.Hsu@amd.com assert(initialized()); 2715769Snate@binkert.org flags = _flags; 2727451SLisa.Hsu@amd.com flags.set(Initialized); 2735769Snate@binkert.org 2747452SLisa.Hsu@amd.com // need to see if original event was in a scheduled, unsquashed 2757452SLisa.Hsu@amd.com // state, but don't want to restore those flags in the current 2767452SLisa.Hsu@amd.com // object itself (since they aren't immediately true) 27710906Sandreas.sandberg@arm.com if (flags.isSet(Scheduled) && !flags.isSet(Squashed)) { 27810906Sandreas.sandberg@arm.com flags.clear(Squashed | Scheduled); 27910906Sandreas.sandberg@arm.com } else { 28010906Sandreas.sandberg@arm.com DPRINTF(Checkpoint, "Event '%s' need to be scheduled @%d\n", 28110906Sandreas.sandberg@arm.com name(), _when); 282224SN/A } 283224SN/A} 284224SN/A 2852SN/Avoid 28610906Sandreas.sandberg@arm.comEventQueue::checkpointReschedule(Event *event) 28710906Sandreas.sandberg@arm.com{ 28810906Sandreas.sandberg@arm.com // It's safe to call insert() directly here since this method 28910906Sandreas.sandberg@arm.com // should only be called when restoring from a checkpoint (which 29010906Sandreas.sandberg@arm.com // happens before thread creation). 29110906Sandreas.sandberg@arm.com if (event->flags.isSet(Event::Scheduled)) 29210906Sandreas.sandberg@arm.com insert(event); 29310906Sandreas.sandberg@arm.com} 29410906Sandreas.sandberg@arm.comvoid 2955501Snate@binkert.orgEventQueue::dump() const 2962SN/A{ 2972SN/A cprintf("============================================================\n"); 2987823Ssteve.reinhardt@amd.com cprintf("EventQueue Dump (cycle %d)\n", curTick()); 2992SN/A cprintf("------------------------------------------------------------\n"); 3002SN/A 3012SN/A if (empty()) 3022SN/A cprintf("<No Events>\n"); 3032SN/A else { 3045502Snate@binkert.org Event *nextBin = head; 3055502Snate@binkert.org while (nextBin) { 3065502Snate@binkert.org Event *nextInBin = nextBin; 3075503Snate@binkert.org while (nextInBin) { 3085503Snate@binkert.org nextInBin->dump(); 3095502Snate@binkert.org nextInBin = nextInBin->nextInBin; 3105503Snate@binkert.org } 3115502Snate@binkert.org 3125502Snate@binkert.org nextBin = nextBin->nextBin; 3132SN/A } 3142SN/A } 3152SN/A 3162SN/A cprintf("============================================================\n"); 3172SN/A} 3182SN/A 3195502Snate@binkert.orgbool 3205502Snate@binkert.orgEventQueue::debugVerify() const 3215502Snate@binkert.org{ 32211168Sandreas.hansson@arm.com std::unordered_map<long, bool> map; 3235502Snate@binkert.org 3245502Snate@binkert.org Tick time = 0; 3255502Snate@binkert.org short priority = 0; 3265502Snate@binkert.org 3275502Snate@binkert.org Event *nextBin = head; 3285502Snate@binkert.org while (nextBin) { 3295503Snate@binkert.org Event *nextInBin = nextBin; 3305503Snate@binkert.org while (nextInBin) { 3315502Snate@binkert.org if (nextInBin->when() < time) { 3325502Snate@binkert.org cprintf("time goes backwards!"); 3335502Snate@binkert.org nextInBin->dump(); 3345502Snate@binkert.org return false; 3355502Snate@binkert.org } else if (nextInBin->when() == time && 3365502Snate@binkert.org nextInBin->priority() < priority) { 3375502Snate@binkert.org cprintf("priority inverted!"); 3385502Snate@binkert.org nextInBin->dump(); 3395502Snate@binkert.org return false; 3405502Snate@binkert.org } 3415502Snate@binkert.org 3425502Snate@binkert.org if (map[reinterpret_cast<long>(nextInBin)]) { 3435502Snate@binkert.org cprintf("Node already seen"); 3445502Snate@binkert.org nextInBin->dump(); 3455502Snate@binkert.org return false; 3465502Snate@binkert.org } 3475502Snate@binkert.org map[reinterpret_cast<long>(nextInBin)] = true; 3485502Snate@binkert.org 3495502Snate@binkert.org time = nextInBin->when(); 3505502Snate@binkert.org priority = nextInBin->priority(); 3515502Snate@binkert.org 3525502Snate@binkert.org nextInBin = nextInBin->nextInBin; 3535503Snate@binkert.org } 3545502Snate@binkert.org 3555502Snate@binkert.org nextBin = nextBin->nextBin; 3565502Snate@binkert.org } 3575502Snate@binkert.org 3585502Snate@binkert.org return true; 3595502Snate@binkert.org} 3605502Snate@binkert.org 3618648Snilay@cs.wisc.eduEvent* 3628648Snilay@cs.wisc.eduEventQueue::replaceHead(Event* s) 3638648Snilay@cs.wisc.edu{ 3648648Snilay@cs.wisc.edu Event* t = head; 3658648Snilay@cs.wisc.edu head = s; 3668648Snilay@cs.wisc.edu return t; 3678648Snilay@cs.wisc.edu} 3688648Snilay@cs.wisc.edu 3691019SN/Avoid 3701019SN/AdumpMainQueue() 3711019SN/A{ 3729983Sstever@gmail.com for (uint32_t i = 0; i < numMainEventQueues; ++i) { 3739983Sstever@gmail.com mainEventQueue[i]->dump(); 3749983Sstever@gmail.com } 3751019SN/A} 3761019SN/A 3772SN/A 3782SN/Aconst char * 3795336Shines@cs.fsu.eduEvent::description() const 3802SN/A{ 3812SN/A return "generic"; 3822SN/A} 3832SN/A 3842SN/Avoid 3852SN/AEvent::trace(const char *action) 3862SN/A{ 3872SN/A // This DPRINTF is unconditional because calls to this function 3882SN/A // are protected by an 'if (DTRACE(Event))' in the inlined Event 3892SN/A // methods. 3902SN/A // 3912SN/A // This is just a default implementation for derived classes where 3922SN/A // it's not worth doing anything special. If you want to put a 3932SN/A // more informative message in the trace, override this method on 3942SN/A // the particular subclass where you have the information that 3952SN/A // needs to be printed. 3962SN/A DPRINTFN("%s event %s @ %d\n", description(), action, when()); 3972SN/A} 3982SN/A 3992SN/Avoid 4005501Snate@binkert.orgEvent::dump() const 4012SN/A{ 4025501Snate@binkert.org cprintf("Event %s (%s)\n", name(), description()); 4035769Snate@binkert.org cprintf("Flags: %#x\n", flags); 4045501Snate@binkert.org#ifdef EVENTQ_DEBUG 4055501Snate@binkert.org cprintf("Created: %d\n", whenCreated); 4062SN/A#endif 4072SN/A if (scheduled()) { 4085501Snate@binkert.org#ifdef EVENTQ_DEBUG 4095501Snate@binkert.org cprintf("Scheduled at %d\n", whenScheduled); 4102SN/A#endif 4111019SN/A cprintf("Scheduled for %d, priority %d\n", when(), _priority); 4125501Snate@binkert.org } else { 4131019SN/A cprintf("Not Scheduled\n"); 4142SN/A } 4152SN/A} 4167063Snate@binkert.org 4177063Snate@binkert.orgEventQueue::EventQueue(const string &n) 41810412Sandreas.hansson@arm.com : objName(n), head(NULL), _curTick(0) 4199983Sstever@gmail.com{ 4209983Sstever@gmail.com} 4219983Sstever@gmail.com 4229983Sstever@gmail.comvoid 4239983Sstever@gmail.comEventQueue::asyncInsert(Event *event) 4249983Sstever@gmail.com{ 42510412Sandreas.hansson@arm.com async_queue_mutex.lock(); 4269983Sstever@gmail.com async_queue.push_back(event); 42710412Sandreas.hansson@arm.com async_queue_mutex.unlock(); 4289983Sstever@gmail.com} 4299983Sstever@gmail.com 4309983Sstever@gmail.comvoid 4319983Sstever@gmail.comEventQueue::handleAsyncInsertions() 4329983Sstever@gmail.com{ 4339983Sstever@gmail.com assert(this == curEventQueue()); 43410412Sandreas.hansson@arm.com async_queue_mutex.lock(); 4359983Sstever@gmail.com 4369983Sstever@gmail.com while (!async_queue.empty()) { 4379983Sstever@gmail.com insert(async_queue.front()); 4389983Sstever@gmail.com async_queue.pop_front(); 4399983Sstever@gmail.com } 4409983Sstever@gmail.com 44110412Sandreas.hansson@arm.com async_queue_mutex.unlock(); 4429983Sstever@gmail.com} 443