queue.hh revision 13449
111375Sandreas.hansson@arm.com/* 212726Snikos.nikoleris@arm.com * Copyright (c) 2012-2013, 2015-2016, 2018 ARM Limited 311375Sandreas.hansson@arm.com * All rights reserved. 411375Sandreas.hansson@arm.com * 511375Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 611375Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 711375Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 811375Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 911375Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 1011375Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 1111375Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 1211375Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 1311375Sandreas.hansson@arm.com * 1411375Sandreas.hansson@arm.com * Copyright (c) 2003-2005 The Regents of The University of Michigan 1511375Sandreas.hansson@arm.com * All rights reserved. 1611375Sandreas.hansson@arm.com * 1711375Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 1811375Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 1911375Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 2011375Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 2111375Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 2211375Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 2311375Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 2411375Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 2511375Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 2611375Sandreas.hansson@arm.com * this software without specific prior written permission. 2711375Sandreas.hansson@arm.com * 2811375Sandreas.hansson@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2911375Sandreas.hansson@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3011375Sandreas.hansson@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3111375Sandreas.hansson@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3211375Sandreas.hansson@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3311375Sandreas.hansson@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3411375Sandreas.hansson@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3511375Sandreas.hansson@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3611375Sandreas.hansson@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3711375Sandreas.hansson@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811375Sandreas.hansson@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3911375Sandreas.hansson@arm.com * 4011375Sandreas.hansson@arm.com * Authors: Erik Hallnor 4111375Sandreas.hansson@arm.com * Andreas Sandberg 4211375Sandreas.hansson@arm.com * Andreas Hansson 4311375Sandreas.hansson@arm.com */ 4411375Sandreas.hansson@arm.com 4511375Sandreas.hansson@arm.com/** @file 4611375Sandreas.hansson@arm.com * Declaration of a high-level queue structure 4711375Sandreas.hansson@arm.com */ 4811375Sandreas.hansson@arm.com 4911375Sandreas.hansson@arm.com#ifndef __MEM_CACHE_QUEUE_HH__ 5011375Sandreas.hansson@arm.com#define __MEM_CACHE_QUEUE_HH__ 5111375Sandreas.hansson@arm.com 5211375Sandreas.hansson@arm.com#include <cassert> 5312727Snikos.nikoleris@arm.com#include <string> 5411375Sandreas.hansson@arm.com 5513449Sgabeblack@google.com#include "base/logging.hh" 5611375Sandreas.hansson@arm.com#include "base/trace.hh" 5712727Snikos.nikoleris@arm.com#include "base/types.hh" 5811375Sandreas.hansson@arm.com#include "debug/Drain.hh" 5911375Sandreas.hansson@arm.com#include "mem/cache/queue_entry.hh" 6012727Snikos.nikoleris@arm.com#include "mem/packet.hh" 6112727Snikos.nikoleris@arm.com#include "sim/core.hh" 6211375Sandreas.hansson@arm.com#include "sim/drain.hh" 6311375Sandreas.hansson@arm.com 6411375Sandreas.hansson@arm.com/** 6511375Sandreas.hansson@arm.com * A high-level queue interface, to be used by both the MSHR queue and 6611375Sandreas.hansson@arm.com * the write buffer. 6711375Sandreas.hansson@arm.com */ 6811375Sandreas.hansson@arm.comtemplate<class Entry> 6911375Sandreas.hansson@arm.comclass Queue : public Drainable 7011375Sandreas.hansson@arm.com{ 7111375Sandreas.hansson@arm.com protected: 7211375Sandreas.hansson@arm.com /** Local label (for functional print requests) */ 7311375Sandreas.hansson@arm.com const std::string label; 7411375Sandreas.hansson@arm.com 7511375Sandreas.hansson@arm.com /** 7611375Sandreas.hansson@arm.com * The total number of entries in this queue. This number is set 7711377Sandreas.hansson@arm.com * as the number of entries requested plus any reserve. This 7811375Sandreas.hansson@arm.com * allows for the same number of effective entries while still 7911375Sandreas.hansson@arm.com * maintaining an overflow reserve. 8011375Sandreas.hansson@arm.com */ 8111375Sandreas.hansson@arm.com const int numEntries; 8211375Sandreas.hansson@arm.com 8311375Sandreas.hansson@arm.com /** 8411375Sandreas.hansson@arm.com * The number of entries to hold as a temporary overflow 8511375Sandreas.hansson@arm.com * space. This is used to allow temporary overflow of the number 8611375Sandreas.hansson@arm.com * of entries as we only check the full condition under certain 8711375Sandreas.hansson@arm.com * conditions. 8811375Sandreas.hansson@arm.com */ 8911375Sandreas.hansson@arm.com const int numReserve; 9011375Sandreas.hansson@arm.com 9111375Sandreas.hansson@arm.com /** Actual storage. */ 9211375Sandreas.hansson@arm.com std::vector<Entry> entries; 9311375Sandreas.hansson@arm.com /** Holds pointers to all allocated entries. */ 9411375Sandreas.hansson@arm.com typename Entry::List allocatedList; 9511375Sandreas.hansson@arm.com /** Holds pointers to entries that haven't been sent downstream. */ 9611375Sandreas.hansson@arm.com typename Entry::List readyList; 9711375Sandreas.hansson@arm.com /** Holds non allocated entries. */ 9811375Sandreas.hansson@arm.com typename Entry::List freeList; 9911375Sandreas.hansson@arm.com 10011375Sandreas.hansson@arm.com typename Entry::Iterator addToReadyList(Entry* entry) 10111375Sandreas.hansson@arm.com { 10211375Sandreas.hansson@arm.com if (readyList.empty() || 10311375Sandreas.hansson@arm.com readyList.back()->readyTime <= entry->readyTime) { 10411375Sandreas.hansson@arm.com return readyList.insert(readyList.end(), entry); 10511375Sandreas.hansson@arm.com } 10611375Sandreas.hansson@arm.com 10711375Sandreas.hansson@arm.com for (auto i = readyList.begin(); i != readyList.end(); ++i) { 10811375Sandreas.hansson@arm.com if ((*i)->readyTime > entry->readyTime) { 10911375Sandreas.hansson@arm.com return readyList.insert(i, entry); 11011375Sandreas.hansson@arm.com } 11111375Sandreas.hansson@arm.com } 11213449Sgabeblack@google.com panic("Failed to add to ready list."); 11311375Sandreas.hansson@arm.com } 11411375Sandreas.hansson@arm.com 11511375Sandreas.hansson@arm.com /** The number of entries that are in service. */ 11611375Sandreas.hansson@arm.com int _numInService; 11711375Sandreas.hansson@arm.com 11811375Sandreas.hansson@arm.com /** The number of currently allocated entries. */ 11911375Sandreas.hansson@arm.com int allocated; 12011375Sandreas.hansson@arm.com 12111375Sandreas.hansson@arm.com public: 12211375Sandreas.hansson@arm.com 12311375Sandreas.hansson@arm.com /** 12411375Sandreas.hansson@arm.com * Create a queue with a given number of entries. 12511375Sandreas.hansson@arm.com * 12611375Sandreas.hansson@arm.com * @param num_entries The number of entries in this queue. 12711377Sandreas.hansson@arm.com * @param reserve The extra overflow entries needed. 12811375Sandreas.hansson@arm.com */ 12911375Sandreas.hansson@arm.com Queue(const std::string &_label, int num_entries, int reserve) : 13011377Sandreas.hansson@arm.com label(_label), numEntries(num_entries + reserve), 13111375Sandreas.hansson@arm.com numReserve(reserve), entries(numEntries), _numInService(0), 13211375Sandreas.hansson@arm.com allocated(0) 13311375Sandreas.hansson@arm.com { 13411375Sandreas.hansson@arm.com for (int i = 0; i < numEntries; ++i) { 13511375Sandreas.hansson@arm.com freeList.push_back(&entries[i]); 13611375Sandreas.hansson@arm.com } 13711375Sandreas.hansson@arm.com } 13811375Sandreas.hansson@arm.com 13911375Sandreas.hansson@arm.com bool isEmpty() const 14011375Sandreas.hansson@arm.com { 14111375Sandreas.hansson@arm.com return allocated == 0; 14211375Sandreas.hansson@arm.com } 14311375Sandreas.hansson@arm.com 14411375Sandreas.hansson@arm.com bool isFull() const 14511375Sandreas.hansson@arm.com { 14611377Sandreas.hansson@arm.com return (allocated >= numEntries - numReserve); 14711375Sandreas.hansson@arm.com } 14811375Sandreas.hansson@arm.com 14911375Sandreas.hansson@arm.com int numInService() const 15011375Sandreas.hansson@arm.com { 15111375Sandreas.hansson@arm.com return _numInService; 15211375Sandreas.hansson@arm.com } 15311375Sandreas.hansson@arm.com 15411375Sandreas.hansson@arm.com /** 15512726Snikos.nikoleris@arm.com * Find the first entry that matches the provided address. 15612726Snikos.nikoleris@arm.com * 15711375Sandreas.hansson@arm.com * @param blk_addr The block address to find. 15811375Sandreas.hansson@arm.com * @param is_secure True if the target memory space is secure. 15912726Snikos.nikoleris@arm.com * @param ignore_uncacheable Should uncacheables be ignored or not 16011375Sandreas.hansson@arm.com * @return Pointer to the matching WriteQueueEntry, null if not found. 16111375Sandreas.hansson@arm.com */ 16212726Snikos.nikoleris@arm.com Entry* findMatch(Addr blk_addr, bool is_secure, 16312726Snikos.nikoleris@arm.com bool ignore_uncacheable = true) const 16411375Sandreas.hansson@arm.com { 16511375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 16611375Sandreas.hansson@arm.com // we ignore any entries allocated for uncacheable 16711375Sandreas.hansson@arm.com // accesses and simply ignore them when matching, in the 16811375Sandreas.hansson@arm.com // cache we never check for matches when adding new 16911375Sandreas.hansson@arm.com // uncacheable entries, and we do not want normal 17011375Sandreas.hansson@arm.com // cacheable accesses being added to an WriteQueueEntry 17111375Sandreas.hansson@arm.com // serving an uncacheable access 17212726Snikos.nikoleris@arm.com if (!(ignore_uncacheable && entry->isUncacheable()) && 17312726Snikos.nikoleris@arm.com entry->blkAddr == blk_addr && entry->isSecure == is_secure) { 17411375Sandreas.hansson@arm.com return entry; 17511375Sandreas.hansson@arm.com } 17611375Sandreas.hansson@arm.com } 17711375Sandreas.hansson@arm.com return nullptr; 17811375Sandreas.hansson@arm.com } 17911375Sandreas.hansson@arm.com 18012823Srmk35@cl.cam.ac.uk bool trySatisfyFunctional(PacketPtr pkt, Addr blk_addr) 18111375Sandreas.hansson@arm.com { 18211375Sandreas.hansson@arm.com pkt->pushLabel(label); 18311375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 18412823Srmk35@cl.cam.ac.uk if (entry->blkAddr == blk_addr && entry->trySatisfyFunctional(pkt)) { 18511375Sandreas.hansson@arm.com pkt->popLabel(); 18611375Sandreas.hansson@arm.com return true; 18711375Sandreas.hansson@arm.com } 18811375Sandreas.hansson@arm.com } 18911375Sandreas.hansson@arm.com pkt->popLabel(); 19011375Sandreas.hansson@arm.com return false; 19111375Sandreas.hansson@arm.com } 19211375Sandreas.hansson@arm.com 19311375Sandreas.hansson@arm.com /** 19411375Sandreas.hansson@arm.com * Find any pending requests that overlap the given request. 19511375Sandreas.hansson@arm.com * @param blk_addr Block address. 19611375Sandreas.hansson@arm.com * @param is_secure True if the target memory space is secure. 19711375Sandreas.hansson@arm.com * @return A pointer to the earliest matching WriteQueueEntry. 19811375Sandreas.hansson@arm.com */ 19911375Sandreas.hansson@arm.com Entry* findPending(Addr blk_addr, bool is_secure) const 20011375Sandreas.hansson@arm.com { 20111375Sandreas.hansson@arm.com for (const auto& entry : readyList) { 20211375Sandreas.hansson@arm.com if (entry->blkAddr == blk_addr && entry->isSecure == is_secure) { 20311375Sandreas.hansson@arm.com return entry; 20411375Sandreas.hansson@arm.com } 20511375Sandreas.hansson@arm.com } 20611375Sandreas.hansson@arm.com return nullptr; 20711375Sandreas.hansson@arm.com } 20811375Sandreas.hansson@arm.com 20911375Sandreas.hansson@arm.com /** 21011375Sandreas.hansson@arm.com * Returns the WriteQueueEntry at the head of the readyList. 21111375Sandreas.hansson@arm.com * @return The next request to service. 21211375Sandreas.hansson@arm.com */ 21311375Sandreas.hansson@arm.com Entry* getNext() const 21411375Sandreas.hansson@arm.com { 21511375Sandreas.hansson@arm.com if (readyList.empty() || readyList.front()->readyTime > curTick()) { 21611484Snikos.nikoleris@arm.com return nullptr; 21711375Sandreas.hansson@arm.com } 21811375Sandreas.hansson@arm.com return readyList.front(); 21911375Sandreas.hansson@arm.com } 22011375Sandreas.hansson@arm.com 22111375Sandreas.hansson@arm.com Tick nextReadyTime() const 22211375Sandreas.hansson@arm.com { 22311375Sandreas.hansson@arm.com return readyList.empty() ? MaxTick : readyList.front()->readyTime; 22411375Sandreas.hansson@arm.com } 22511375Sandreas.hansson@arm.com 22611375Sandreas.hansson@arm.com /** 22711375Sandreas.hansson@arm.com * Removes the given entry from the queue. This places the entry 22811375Sandreas.hansson@arm.com * on the free list. 22911375Sandreas.hansson@arm.com * 23011375Sandreas.hansson@arm.com * @param entry 23111375Sandreas.hansson@arm.com */ 23211375Sandreas.hansson@arm.com void deallocate(Entry *entry) 23311375Sandreas.hansson@arm.com { 23411375Sandreas.hansson@arm.com allocatedList.erase(entry->allocIter); 23511375Sandreas.hansson@arm.com freeList.push_front(entry); 23611375Sandreas.hansson@arm.com allocated--; 23711375Sandreas.hansson@arm.com if (entry->inService) { 23811375Sandreas.hansson@arm.com _numInService--; 23911375Sandreas.hansson@arm.com } else { 24011375Sandreas.hansson@arm.com readyList.erase(entry->readyIter); 24111375Sandreas.hansson@arm.com } 24211375Sandreas.hansson@arm.com entry->deallocate(); 24311375Sandreas.hansson@arm.com if (drainState() == DrainState::Draining && allocated == 0) { 24411375Sandreas.hansson@arm.com // Notify the drain manager that we have completed 24511375Sandreas.hansson@arm.com // draining if there are no other outstanding requests in 24611375Sandreas.hansson@arm.com // this queue. 24711375Sandreas.hansson@arm.com DPRINTF(Drain, "Queue now empty, signalling drained\n"); 24811375Sandreas.hansson@arm.com signalDrainDone(); 24911375Sandreas.hansson@arm.com } 25011375Sandreas.hansson@arm.com } 25111375Sandreas.hansson@arm.com 25211375Sandreas.hansson@arm.com DrainState drain() override 25311375Sandreas.hansson@arm.com { 25411375Sandreas.hansson@arm.com return allocated == 0 ? DrainState::Drained : DrainState::Draining; 25511375Sandreas.hansson@arm.com } 25611375Sandreas.hansson@arm.com}; 25711375Sandreas.hansson@arm.com 25811375Sandreas.hansson@arm.com#endif //__MEM_CACHE_QUEUE_HH__ 259