queue.hh revision 11377
111375Sandreas.hansson@arm.com/* 211375Sandreas.hansson@arm.com * Copyright (c) 2012-2013, 2015-2016 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> 5311375Sandreas.hansson@arm.com 5411375Sandreas.hansson@arm.com#include "base/trace.hh" 5511375Sandreas.hansson@arm.com#include "debug/Drain.hh" 5611375Sandreas.hansson@arm.com#include "mem/cache/queue_entry.hh" 5711375Sandreas.hansson@arm.com#include "sim/drain.hh" 5811375Sandreas.hansson@arm.com 5911375Sandreas.hansson@arm.com/** 6011375Sandreas.hansson@arm.com * A high-level queue interface, to be used by both the MSHR queue and 6111375Sandreas.hansson@arm.com * the write buffer. 6211375Sandreas.hansson@arm.com */ 6311375Sandreas.hansson@arm.comtemplate<class Entry> 6411375Sandreas.hansson@arm.comclass Queue : public Drainable 6511375Sandreas.hansson@arm.com{ 6611375Sandreas.hansson@arm.com protected: 6711375Sandreas.hansson@arm.com /** Local label (for functional print requests) */ 6811375Sandreas.hansson@arm.com const std::string label; 6911375Sandreas.hansson@arm.com 7011375Sandreas.hansson@arm.com /** 7111375Sandreas.hansson@arm.com * The total number of entries in this queue. This number is set 7211377Sandreas.hansson@arm.com * as the number of entries requested plus any reserve. This 7311375Sandreas.hansson@arm.com * allows for the same number of effective entries while still 7411375Sandreas.hansson@arm.com * maintaining an overflow reserve. 7511375Sandreas.hansson@arm.com */ 7611375Sandreas.hansson@arm.com const int numEntries; 7711375Sandreas.hansson@arm.com 7811375Sandreas.hansson@arm.com /** 7911375Sandreas.hansson@arm.com * The number of entries to hold as a temporary overflow 8011375Sandreas.hansson@arm.com * space. This is used to allow temporary overflow of the number 8111375Sandreas.hansson@arm.com * of entries as we only check the full condition under certain 8211375Sandreas.hansson@arm.com * conditions. 8311375Sandreas.hansson@arm.com */ 8411375Sandreas.hansson@arm.com const int numReserve; 8511375Sandreas.hansson@arm.com 8611375Sandreas.hansson@arm.com /** Actual storage. */ 8711375Sandreas.hansson@arm.com std::vector<Entry> entries; 8811375Sandreas.hansson@arm.com /** Holds pointers to all allocated entries. */ 8911375Sandreas.hansson@arm.com typename Entry::List allocatedList; 9011375Sandreas.hansson@arm.com /** Holds pointers to entries that haven't been sent downstream. */ 9111375Sandreas.hansson@arm.com typename Entry::List readyList; 9211375Sandreas.hansson@arm.com /** Holds non allocated entries. */ 9311375Sandreas.hansson@arm.com typename Entry::List freeList; 9411375Sandreas.hansson@arm.com 9511375Sandreas.hansson@arm.com typename Entry::Iterator addToReadyList(Entry* entry) 9611375Sandreas.hansson@arm.com { 9711375Sandreas.hansson@arm.com if (readyList.empty() || 9811375Sandreas.hansson@arm.com readyList.back()->readyTime <= entry->readyTime) { 9911375Sandreas.hansson@arm.com return readyList.insert(readyList.end(), entry); 10011375Sandreas.hansson@arm.com } 10111375Sandreas.hansson@arm.com 10211375Sandreas.hansson@arm.com for (auto i = readyList.begin(); i != readyList.end(); ++i) { 10311375Sandreas.hansson@arm.com if ((*i)->readyTime > entry->readyTime) { 10411375Sandreas.hansson@arm.com return readyList.insert(i, entry); 10511375Sandreas.hansson@arm.com } 10611375Sandreas.hansson@arm.com } 10711375Sandreas.hansson@arm.com assert(false); 10811375Sandreas.hansson@arm.com return readyList.end(); // keep stupid compilers happy 10911375Sandreas.hansson@arm.com } 11011375Sandreas.hansson@arm.com 11111375Sandreas.hansson@arm.com /** The number of entries that are in service. */ 11211375Sandreas.hansson@arm.com int _numInService; 11311375Sandreas.hansson@arm.com 11411375Sandreas.hansson@arm.com /** The number of currently allocated entries. */ 11511375Sandreas.hansson@arm.com int allocated; 11611375Sandreas.hansson@arm.com 11711375Sandreas.hansson@arm.com public: 11811375Sandreas.hansson@arm.com 11911375Sandreas.hansson@arm.com /** 12011375Sandreas.hansson@arm.com * Create a queue with a given number of entries. 12111375Sandreas.hansson@arm.com * 12211375Sandreas.hansson@arm.com * @param num_entries The number of entries in this queue. 12311377Sandreas.hansson@arm.com * @param reserve The extra overflow entries needed. 12411375Sandreas.hansson@arm.com */ 12511375Sandreas.hansson@arm.com Queue(const std::string &_label, int num_entries, int reserve) : 12611377Sandreas.hansson@arm.com label(_label), numEntries(num_entries + reserve), 12711375Sandreas.hansson@arm.com numReserve(reserve), entries(numEntries), _numInService(0), 12811375Sandreas.hansson@arm.com allocated(0) 12911375Sandreas.hansson@arm.com { 13011375Sandreas.hansson@arm.com for (int i = 0; i < numEntries; ++i) { 13111375Sandreas.hansson@arm.com freeList.push_back(&entries[i]); 13211375Sandreas.hansson@arm.com } 13311375Sandreas.hansson@arm.com } 13411375Sandreas.hansson@arm.com 13511375Sandreas.hansson@arm.com bool isEmpty() const 13611375Sandreas.hansson@arm.com { 13711375Sandreas.hansson@arm.com return allocated == 0; 13811375Sandreas.hansson@arm.com } 13911375Sandreas.hansson@arm.com 14011375Sandreas.hansson@arm.com bool isFull() const 14111375Sandreas.hansson@arm.com { 14211377Sandreas.hansson@arm.com return (allocated >= numEntries - numReserve); 14311375Sandreas.hansson@arm.com } 14411375Sandreas.hansson@arm.com 14511375Sandreas.hansson@arm.com int numInService() const 14611375Sandreas.hansson@arm.com { 14711375Sandreas.hansson@arm.com return _numInService; 14811375Sandreas.hansson@arm.com } 14911375Sandreas.hansson@arm.com 15011375Sandreas.hansson@arm.com /** 15111375Sandreas.hansson@arm.com * Find the first WriteQueueEntry that matches the provided address. 15211375Sandreas.hansson@arm.com * @param blk_addr The block address to find. 15311375Sandreas.hansson@arm.com * @param is_secure True if the target memory space is secure. 15411375Sandreas.hansson@arm.com * @return Pointer to the matching WriteQueueEntry, null if not found. 15511375Sandreas.hansson@arm.com */ 15611375Sandreas.hansson@arm.com Entry* findMatch(Addr blk_addr, bool is_secure) const 15711375Sandreas.hansson@arm.com { 15811375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 15911375Sandreas.hansson@arm.com // we ignore any entries allocated for uncacheable 16011375Sandreas.hansson@arm.com // accesses and simply ignore them when matching, in the 16111375Sandreas.hansson@arm.com // cache we never check for matches when adding new 16211375Sandreas.hansson@arm.com // uncacheable entries, and we do not want normal 16311375Sandreas.hansson@arm.com // cacheable accesses being added to an WriteQueueEntry 16411375Sandreas.hansson@arm.com // serving an uncacheable access 16511375Sandreas.hansson@arm.com if (!entry->isUncacheable() && entry->blkAddr == blk_addr && 16611375Sandreas.hansson@arm.com entry->isSecure == is_secure) { 16711375Sandreas.hansson@arm.com return entry; 16811375Sandreas.hansson@arm.com } 16911375Sandreas.hansson@arm.com } 17011375Sandreas.hansson@arm.com return nullptr; 17111375Sandreas.hansson@arm.com } 17211375Sandreas.hansson@arm.com 17311375Sandreas.hansson@arm.com bool checkFunctional(PacketPtr pkt, Addr blk_addr) 17411375Sandreas.hansson@arm.com { 17511375Sandreas.hansson@arm.com pkt->pushLabel(label); 17611375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 17711375Sandreas.hansson@arm.com if (entry->blkAddr == blk_addr && entry->checkFunctional(pkt)) { 17811375Sandreas.hansson@arm.com pkt->popLabel(); 17911375Sandreas.hansson@arm.com return true; 18011375Sandreas.hansson@arm.com } 18111375Sandreas.hansson@arm.com } 18211375Sandreas.hansson@arm.com pkt->popLabel(); 18311375Sandreas.hansson@arm.com return false; 18411375Sandreas.hansson@arm.com } 18511375Sandreas.hansson@arm.com 18611375Sandreas.hansson@arm.com /** 18711375Sandreas.hansson@arm.com * Find any pending requests that overlap the given request. 18811375Sandreas.hansson@arm.com * @param blk_addr Block address. 18911375Sandreas.hansson@arm.com * @param is_secure True if the target memory space is secure. 19011375Sandreas.hansson@arm.com * @return A pointer to the earliest matching WriteQueueEntry. 19111375Sandreas.hansson@arm.com */ 19211375Sandreas.hansson@arm.com Entry* findPending(Addr blk_addr, bool is_secure) const 19311375Sandreas.hansson@arm.com { 19411375Sandreas.hansson@arm.com for (const auto& entry : readyList) { 19511375Sandreas.hansson@arm.com if (entry->blkAddr == blk_addr && entry->isSecure == is_secure) { 19611375Sandreas.hansson@arm.com return entry; 19711375Sandreas.hansson@arm.com } 19811375Sandreas.hansson@arm.com } 19911375Sandreas.hansson@arm.com return nullptr; 20011375Sandreas.hansson@arm.com } 20111375Sandreas.hansson@arm.com 20211375Sandreas.hansson@arm.com /** 20311375Sandreas.hansson@arm.com * Returns the WriteQueueEntry at the head of the readyList. 20411375Sandreas.hansson@arm.com * @return The next request to service. 20511375Sandreas.hansson@arm.com */ 20611375Sandreas.hansson@arm.com Entry* getNext() const 20711375Sandreas.hansson@arm.com { 20811375Sandreas.hansson@arm.com if (readyList.empty() || readyList.front()->readyTime > curTick()) { 20911375Sandreas.hansson@arm.com return NULL; 21011375Sandreas.hansson@arm.com } 21111375Sandreas.hansson@arm.com return readyList.front(); 21211375Sandreas.hansson@arm.com } 21311375Sandreas.hansson@arm.com 21411375Sandreas.hansson@arm.com Tick nextReadyTime() const 21511375Sandreas.hansson@arm.com { 21611375Sandreas.hansson@arm.com return readyList.empty() ? MaxTick : readyList.front()->readyTime; 21711375Sandreas.hansson@arm.com } 21811375Sandreas.hansson@arm.com 21911375Sandreas.hansson@arm.com /** 22011375Sandreas.hansson@arm.com * Removes the given entry from the queue. This places the entry 22111375Sandreas.hansson@arm.com * on the free list. 22211375Sandreas.hansson@arm.com * 22311375Sandreas.hansson@arm.com * @param entry 22411375Sandreas.hansson@arm.com */ 22511375Sandreas.hansson@arm.com void deallocate(Entry *entry) 22611375Sandreas.hansson@arm.com { 22711375Sandreas.hansson@arm.com allocatedList.erase(entry->allocIter); 22811375Sandreas.hansson@arm.com freeList.push_front(entry); 22911375Sandreas.hansson@arm.com allocated--; 23011375Sandreas.hansson@arm.com if (entry->inService) { 23111375Sandreas.hansson@arm.com _numInService--; 23211375Sandreas.hansson@arm.com } else { 23311375Sandreas.hansson@arm.com readyList.erase(entry->readyIter); 23411375Sandreas.hansson@arm.com } 23511375Sandreas.hansson@arm.com entry->deallocate(); 23611375Sandreas.hansson@arm.com if (drainState() == DrainState::Draining && allocated == 0) { 23711375Sandreas.hansson@arm.com // Notify the drain manager that we have completed 23811375Sandreas.hansson@arm.com // draining if there are no other outstanding requests in 23911375Sandreas.hansson@arm.com // this queue. 24011375Sandreas.hansson@arm.com DPRINTF(Drain, "Queue now empty, signalling drained\n"); 24111375Sandreas.hansson@arm.com signalDrainDone(); 24211375Sandreas.hansson@arm.com } 24311375Sandreas.hansson@arm.com } 24411375Sandreas.hansson@arm.com 24511375Sandreas.hansson@arm.com DrainState drain() override 24611375Sandreas.hansson@arm.com { 24711375Sandreas.hansson@arm.com return allocated == 0 ? DrainState::Drained : DrainState::Draining; 24811375Sandreas.hansson@arm.com } 24911375Sandreas.hansson@arm.com}; 25011375Sandreas.hansson@arm.com 25111375Sandreas.hansson@arm.com#endif //__MEM_CACHE_QUEUE_HH__ 252