eventq.cc revision 12334
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 4112334Sgabeblack@google.com#include "base/logging.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()) { 23012040Sandreas.sandberg@arm.com assert(!event->flags.isSet(Event::Managed) || 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 23812040Sandreas.sandberg@arm.com event->release(); 2392667Sstever@eecs.umich.edu 2402667Sstever@eecs.umich.edu return NULL; 2412SN/A} 2422SN/A 243224SN/Avoid 24410905Sandreas.sandberg@arm.comEvent::serialize(CheckpointOut &cp) const 245224SN/A{ 246224SN/A SERIALIZE_SCALAR(_when); 247224SN/A SERIALIZE_SCALAR(_priority); 2485769Snate@binkert.org short _flags = flags; 2495769Snate@binkert.org SERIALIZE_SCALAR(_flags); 250224SN/A} 251224SN/A 252224SN/Avoid 25310905Sandreas.sandberg@arm.comEvent::unserialize(CheckpointIn &cp) 254224SN/A{ 25510906Sandreas.sandberg@arm.com assert(!scheduled()); 256224SN/A 257224SN/A UNSERIALIZE_SCALAR(_when); 258224SN/A UNSERIALIZE_SCALAR(_priority); 259224SN/A 26010906Sandreas.sandberg@arm.com FlagsType _flags; 2615769Snate@binkert.org UNSERIALIZE_SCALAR(_flags); 2627452SLisa.Hsu@amd.com 2637452SLisa.Hsu@amd.com // Old checkpoints had no concept of the Initialized flag 2647452SLisa.Hsu@amd.com // so restoring from old checkpoints always fail. 26511320Ssteve.reinhardt@amd.com // Events are initialized on construction but original code 26611320Ssteve.reinhardt@amd.com // "flags = _flags" would just overwrite the initialization. 26711320Ssteve.reinhardt@amd.com // So, read in the checkpoint flags, but then set the Initialized 2687452SLisa.Hsu@amd.com // flag on top of it in order to avoid failures. 2697451SLisa.Hsu@amd.com assert(initialized()); 2705769Snate@binkert.org flags = _flags; 2717451SLisa.Hsu@amd.com flags.set(Initialized); 2725769Snate@binkert.org 2737452SLisa.Hsu@amd.com // need to see if original event was in a scheduled, unsquashed 2747452SLisa.Hsu@amd.com // state, but don't want to restore those flags in the current 2757452SLisa.Hsu@amd.com // object itself (since they aren't immediately true) 27610906Sandreas.sandberg@arm.com if (flags.isSet(Scheduled) && !flags.isSet(Squashed)) { 27710906Sandreas.sandberg@arm.com flags.clear(Squashed | Scheduled); 27810906Sandreas.sandberg@arm.com } else { 27910906Sandreas.sandberg@arm.com DPRINTF(Checkpoint, "Event '%s' need to be scheduled @%d\n", 28010906Sandreas.sandberg@arm.com name(), _when); 281224SN/A } 282224SN/A} 283224SN/A 2842SN/Avoid 28510906Sandreas.sandberg@arm.comEventQueue::checkpointReschedule(Event *event) 28610906Sandreas.sandberg@arm.com{ 28710906Sandreas.sandberg@arm.com // It's safe to call insert() directly here since this method 28810906Sandreas.sandberg@arm.com // should only be called when restoring from a checkpoint (which 28910906Sandreas.sandberg@arm.com // happens before thread creation). 29010906Sandreas.sandberg@arm.com if (event->flags.isSet(Event::Scheduled)) 29110906Sandreas.sandberg@arm.com insert(event); 29210906Sandreas.sandberg@arm.com} 29310906Sandreas.sandberg@arm.comvoid 2945501Snate@binkert.orgEventQueue::dump() const 2952SN/A{ 2962SN/A cprintf("============================================================\n"); 2977823Ssteve.reinhardt@amd.com cprintf("EventQueue Dump (cycle %d)\n", curTick()); 2982SN/A cprintf("------------------------------------------------------------\n"); 2992SN/A 3002SN/A if (empty()) 3012SN/A cprintf("<No Events>\n"); 3022SN/A else { 3035502Snate@binkert.org Event *nextBin = head; 3045502Snate@binkert.org while (nextBin) { 3055502Snate@binkert.org Event *nextInBin = nextBin; 3065503Snate@binkert.org while (nextInBin) { 3075503Snate@binkert.org nextInBin->dump(); 3085502Snate@binkert.org nextInBin = nextInBin->nextInBin; 3095503Snate@binkert.org } 3105502Snate@binkert.org 3115502Snate@binkert.org nextBin = nextBin->nextBin; 3122SN/A } 3132SN/A } 3142SN/A 3152SN/A cprintf("============================================================\n"); 3162SN/A} 3172SN/A 3185502Snate@binkert.orgbool 3195502Snate@binkert.orgEventQueue::debugVerify() const 3205502Snate@binkert.org{ 32111168Sandreas.hansson@arm.com std::unordered_map<long, bool> map; 3225502Snate@binkert.org 3235502Snate@binkert.org Tick time = 0; 3245502Snate@binkert.org short priority = 0; 3255502Snate@binkert.org 3265502Snate@binkert.org Event *nextBin = head; 3275502Snate@binkert.org while (nextBin) { 3285503Snate@binkert.org Event *nextInBin = nextBin; 3295503Snate@binkert.org while (nextInBin) { 3305502Snate@binkert.org if (nextInBin->when() < time) { 3315502Snate@binkert.org cprintf("time goes backwards!"); 3325502Snate@binkert.org nextInBin->dump(); 3335502Snate@binkert.org return false; 3345502Snate@binkert.org } else if (nextInBin->when() == time && 3355502Snate@binkert.org nextInBin->priority() < priority) { 3365502Snate@binkert.org cprintf("priority inverted!"); 3375502Snate@binkert.org nextInBin->dump(); 3385502Snate@binkert.org return false; 3395502Snate@binkert.org } 3405502Snate@binkert.org 3415502Snate@binkert.org if (map[reinterpret_cast<long>(nextInBin)]) { 3425502Snate@binkert.org cprintf("Node already seen"); 3435502Snate@binkert.org nextInBin->dump(); 3445502Snate@binkert.org return false; 3455502Snate@binkert.org } 3465502Snate@binkert.org map[reinterpret_cast<long>(nextInBin)] = true; 3475502Snate@binkert.org 3485502Snate@binkert.org time = nextInBin->when(); 3495502Snate@binkert.org priority = nextInBin->priority(); 3505502Snate@binkert.org 3515502Snate@binkert.org nextInBin = nextInBin->nextInBin; 3525503Snate@binkert.org } 3535502Snate@binkert.org 3545502Snate@binkert.org nextBin = nextBin->nextBin; 3555502Snate@binkert.org } 3565502Snate@binkert.org 3575502Snate@binkert.org return true; 3585502Snate@binkert.org} 3595502Snate@binkert.org 3608648Snilay@cs.wisc.eduEvent* 3618648Snilay@cs.wisc.eduEventQueue::replaceHead(Event* s) 3628648Snilay@cs.wisc.edu{ 3638648Snilay@cs.wisc.edu Event* t = head; 3648648Snilay@cs.wisc.edu head = s; 3658648Snilay@cs.wisc.edu return t; 3668648Snilay@cs.wisc.edu} 3678648Snilay@cs.wisc.edu 3681019SN/Avoid 3691019SN/AdumpMainQueue() 3701019SN/A{ 3719983Sstever@gmail.com for (uint32_t i = 0; i < numMainEventQueues; ++i) { 3729983Sstever@gmail.com mainEventQueue[i]->dump(); 3739983Sstever@gmail.com } 3741019SN/A} 3751019SN/A 3762SN/A 3772SN/Aconst char * 3785336Shines@cs.fsu.eduEvent::description() const 3792SN/A{ 3802SN/A return "generic"; 3812SN/A} 3822SN/A 3832SN/Avoid 3842SN/AEvent::trace(const char *action) 3852SN/A{ 3862SN/A // This DPRINTF is unconditional because calls to this function 3872SN/A // are protected by an 'if (DTRACE(Event))' in the inlined Event 3882SN/A // methods. 3892SN/A // 3902SN/A // This is just a default implementation for derived classes where 3912SN/A // it's not worth doing anything special. If you want to put a 3922SN/A // more informative message in the trace, override this method on 3932SN/A // the particular subclass where you have the information that 3942SN/A // needs to be printed. 3952SN/A DPRINTFN("%s event %s @ %d\n", description(), action, when()); 3962SN/A} 3972SN/A 3982SN/Avoid 3995501Snate@binkert.orgEvent::dump() const 4002SN/A{ 4015501Snate@binkert.org cprintf("Event %s (%s)\n", name(), description()); 4025769Snate@binkert.org cprintf("Flags: %#x\n", flags); 4035501Snate@binkert.org#ifdef EVENTQ_DEBUG 4045501Snate@binkert.org cprintf("Created: %d\n", whenCreated); 4052SN/A#endif 4062SN/A if (scheduled()) { 4075501Snate@binkert.org#ifdef EVENTQ_DEBUG 4085501Snate@binkert.org cprintf("Scheduled at %d\n", whenScheduled); 4092SN/A#endif 4101019SN/A cprintf("Scheduled for %d, priority %d\n", when(), _priority); 4115501Snate@binkert.org } else { 4121019SN/A cprintf("Not Scheduled\n"); 4132SN/A } 4142SN/A} 4157063Snate@binkert.org 4167063Snate@binkert.orgEventQueue::EventQueue(const string &n) 41710412Sandreas.hansson@arm.com : objName(n), head(NULL), _curTick(0) 4189983Sstever@gmail.com{ 4199983Sstever@gmail.com} 4209983Sstever@gmail.com 4219983Sstever@gmail.comvoid 4229983Sstever@gmail.comEventQueue::asyncInsert(Event *event) 4239983Sstever@gmail.com{ 42410412Sandreas.hansson@arm.com async_queue_mutex.lock(); 4259983Sstever@gmail.com async_queue.push_back(event); 42610412Sandreas.hansson@arm.com async_queue_mutex.unlock(); 4279983Sstever@gmail.com} 4289983Sstever@gmail.com 4299983Sstever@gmail.comvoid 4309983Sstever@gmail.comEventQueue::handleAsyncInsertions() 4319983Sstever@gmail.com{ 4329983Sstever@gmail.com assert(this == curEventQueue()); 43310412Sandreas.hansson@arm.com async_queue_mutex.lock(); 4349983Sstever@gmail.com 4359983Sstever@gmail.com while (!async_queue.empty()) { 4369983Sstever@gmail.com insert(async_queue.front()); 4379983Sstever@gmail.com async_queue.pop_front(); 4389983Sstever@gmail.com } 4399983Sstever@gmail.com 44010412Sandreas.hansson@arm.com async_queue_mutex.unlock(); 4419983Sstever@gmail.com} 442