queue.hh revision 13861
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> 5413858Sodanrc@yahoo.com.br#include <type_traits> 5511375Sandreas.hansson@arm.com 5613449Sgabeblack@google.com#include "base/logging.hh" 5711375Sandreas.hansson@arm.com#include "base/trace.hh" 5812727Snikos.nikoleris@arm.com#include "base/types.hh" 5911375Sandreas.hansson@arm.com#include "debug/Drain.hh" 6011375Sandreas.hansson@arm.com#include "mem/cache/queue_entry.hh" 6112727Snikos.nikoleris@arm.com#include "mem/packet.hh" 6212727Snikos.nikoleris@arm.com#include "sim/core.hh" 6311375Sandreas.hansson@arm.com#include "sim/drain.hh" 6411375Sandreas.hansson@arm.com 6511375Sandreas.hansson@arm.com/** 6611375Sandreas.hansson@arm.com * A high-level queue interface, to be used by both the MSHR queue and 6711375Sandreas.hansson@arm.com * the write buffer. 6811375Sandreas.hansson@arm.com */ 6911375Sandreas.hansson@arm.comtemplate<class Entry> 7011375Sandreas.hansson@arm.comclass Queue : public Drainable 7111375Sandreas.hansson@arm.com{ 7213858Sodanrc@yahoo.com.br static_assert(std::is_base_of<QueueEntry, Entry>::value, 7313858Sodanrc@yahoo.com.br "Entry must be derived from QueueEntry"); 7413858Sodanrc@yahoo.com.br 7511375Sandreas.hansson@arm.com protected: 7611375Sandreas.hansson@arm.com /** Local label (for functional print requests) */ 7711375Sandreas.hansson@arm.com const std::string label; 7811375Sandreas.hansson@arm.com 7911375Sandreas.hansson@arm.com /** 8011375Sandreas.hansson@arm.com * The total number of entries in this queue. This number is set 8111377Sandreas.hansson@arm.com * as the number of entries requested plus any reserve. This 8211375Sandreas.hansson@arm.com * allows for the same number of effective entries while still 8311375Sandreas.hansson@arm.com * maintaining an overflow reserve. 8411375Sandreas.hansson@arm.com */ 8511375Sandreas.hansson@arm.com const int numEntries; 8611375Sandreas.hansson@arm.com 8711375Sandreas.hansson@arm.com /** 8811375Sandreas.hansson@arm.com * The number of entries to hold as a temporary overflow 8911375Sandreas.hansson@arm.com * space. This is used to allow temporary overflow of the number 9011375Sandreas.hansson@arm.com * of entries as we only check the full condition under certain 9111375Sandreas.hansson@arm.com * conditions. 9211375Sandreas.hansson@arm.com */ 9311375Sandreas.hansson@arm.com const int numReserve; 9411375Sandreas.hansson@arm.com 9511375Sandreas.hansson@arm.com /** Actual storage. */ 9611375Sandreas.hansson@arm.com std::vector<Entry> entries; 9711375Sandreas.hansson@arm.com /** Holds pointers to all allocated entries. */ 9811375Sandreas.hansson@arm.com typename Entry::List allocatedList; 9911375Sandreas.hansson@arm.com /** Holds pointers to entries that haven't been sent downstream. */ 10011375Sandreas.hansson@arm.com typename Entry::List readyList; 10111375Sandreas.hansson@arm.com /** Holds non allocated entries. */ 10211375Sandreas.hansson@arm.com typename Entry::List freeList; 10311375Sandreas.hansson@arm.com 10411375Sandreas.hansson@arm.com typename Entry::Iterator addToReadyList(Entry* entry) 10511375Sandreas.hansson@arm.com { 10611375Sandreas.hansson@arm.com if (readyList.empty() || 10711375Sandreas.hansson@arm.com readyList.back()->readyTime <= entry->readyTime) { 10811375Sandreas.hansson@arm.com return readyList.insert(readyList.end(), entry); 10911375Sandreas.hansson@arm.com } 11011375Sandreas.hansson@arm.com 11111375Sandreas.hansson@arm.com for (auto i = readyList.begin(); i != readyList.end(); ++i) { 11211375Sandreas.hansson@arm.com if ((*i)->readyTime > entry->readyTime) { 11311375Sandreas.hansson@arm.com return readyList.insert(i, entry); 11411375Sandreas.hansson@arm.com } 11511375Sandreas.hansson@arm.com } 11613449Sgabeblack@google.com panic("Failed to add to ready list."); 11711375Sandreas.hansson@arm.com } 11811375Sandreas.hansson@arm.com 11911375Sandreas.hansson@arm.com /** The number of entries that are in service. */ 12011375Sandreas.hansson@arm.com int _numInService; 12111375Sandreas.hansson@arm.com 12211375Sandreas.hansson@arm.com /** The number of currently allocated entries. */ 12311375Sandreas.hansson@arm.com int allocated; 12411375Sandreas.hansson@arm.com 12511375Sandreas.hansson@arm.com public: 12611375Sandreas.hansson@arm.com 12711375Sandreas.hansson@arm.com /** 12811375Sandreas.hansson@arm.com * Create a queue with a given number of entries. 12911375Sandreas.hansson@arm.com * 13011375Sandreas.hansson@arm.com * @param num_entries The number of entries in this queue. 13111377Sandreas.hansson@arm.com * @param reserve The extra overflow entries needed. 13211375Sandreas.hansson@arm.com */ 13311375Sandreas.hansson@arm.com Queue(const std::string &_label, int num_entries, int reserve) : 13411377Sandreas.hansson@arm.com label(_label), numEntries(num_entries + reserve), 13511375Sandreas.hansson@arm.com numReserve(reserve), entries(numEntries), _numInService(0), 13611375Sandreas.hansson@arm.com allocated(0) 13711375Sandreas.hansson@arm.com { 13811375Sandreas.hansson@arm.com for (int i = 0; i < numEntries; ++i) { 13911375Sandreas.hansson@arm.com freeList.push_back(&entries[i]); 14011375Sandreas.hansson@arm.com } 14111375Sandreas.hansson@arm.com } 14211375Sandreas.hansson@arm.com 14311375Sandreas.hansson@arm.com bool isEmpty() const 14411375Sandreas.hansson@arm.com { 14511375Sandreas.hansson@arm.com return allocated == 0; 14611375Sandreas.hansson@arm.com } 14711375Sandreas.hansson@arm.com 14811375Sandreas.hansson@arm.com bool isFull() const 14911375Sandreas.hansson@arm.com { 15011377Sandreas.hansson@arm.com return (allocated >= numEntries - numReserve); 15111375Sandreas.hansson@arm.com } 15211375Sandreas.hansson@arm.com 15311375Sandreas.hansson@arm.com int numInService() const 15411375Sandreas.hansson@arm.com { 15511375Sandreas.hansson@arm.com return _numInService; 15611375Sandreas.hansson@arm.com } 15711375Sandreas.hansson@arm.com 15811375Sandreas.hansson@arm.com /** 15912726Snikos.nikoleris@arm.com * Find the first entry that matches the provided address. 16012726Snikos.nikoleris@arm.com * 16111375Sandreas.hansson@arm.com * @param blk_addr The block address to find. 16211375Sandreas.hansson@arm.com * @param is_secure True if the target memory space is secure. 16312726Snikos.nikoleris@arm.com * @param ignore_uncacheable Should uncacheables be ignored or not 16411375Sandreas.hansson@arm.com * @return Pointer to the matching WriteQueueEntry, null if not found. 16511375Sandreas.hansson@arm.com */ 16612726Snikos.nikoleris@arm.com Entry* findMatch(Addr blk_addr, bool is_secure, 16712726Snikos.nikoleris@arm.com bool ignore_uncacheable = true) const 16811375Sandreas.hansson@arm.com { 16911375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 17011375Sandreas.hansson@arm.com // we ignore any entries allocated for uncacheable 17111375Sandreas.hansson@arm.com // accesses and simply ignore them when matching, in the 17211375Sandreas.hansson@arm.com // cache we never check for matches when adding new 17311375Sandreas.hansson@arm.com // uncacheable entries, and we do not want normal 17411375Sandreas.hansson@arm.com // cacheable accesses being added to an WriteQueueEntry 17511375Sandreas.hansson@arm.com // serving an uncacheable access 17612726Snikos.nikoleris@arm.com if (!(ignore_uncacheable && entry->isUncacheable()) && 17713861Sodanrc@yahoo.com.br entry->matchBlockAddr(blk_addr, is_secure)) { 17811375Sandreas.hansson@arm.com return entry; 17911375Sandreas.hansson@arm.com } 18011375Sandreas.hansson@arm.com } 18111375Sandreas.hansson@arm.com return nullptr; 18211375Sandreas.hansson@arm.com } 18311375Sandreas.hansson@arm.com 18412823Srmk35@cl.cam.ac.uk bool trySatisfyFunctional(PacketPtr pkt, Addr blk_addr) 18511375Sandreas.hansson@arm.com { 18611375Sandreas.hansson@arm.com pkt->pushLabel(label); 18711375Sandreas.hansson@arm.com for (const auto& entry : allocatedList) { 18813861Sodanrc@yahoo.com.br if (entry->matchBlockAddr(blk_addr, pkt->isSecure()) && 18913861Sodanrc@yahoo.com.br entry->trySatisfyFunctional(pkt)) { 19011375Sandreas.hansson@arm.com pkt->popLabel(); 19111375Sandreas.hansson@arm.com return true; 19211375Sandreas.hansson@arm.com } 19311375Sandreas.hansson@arm.com } 19411375Sandreas.hansson@arm.com pkt->popLabel(); 19511375Sandreas.hansson@arm.com return false; 19611375Sandreas.hansson@arm.com } 19711375Sandreas.hansson@arm.com 19811375Sandreas.hansson@arm.com /** 19913861Sodanrc@yahoo.com.br * Find any pending requests that overlap the given request of a 20013861Sodanrc@yahoo.com.br * different queue. 20113861Sodanrc@yahoo.com.br * 20213861Sodanrc@yahoo.com.br * @param entry The entry to be compared against. 20313861Sodanrc@yahoo.com.br * @return A pointer to the earliest matching entry. 20411375Sandreas.hansson@arm.com */ 20513861Sodanrc@yahoo.com.br Entry* findPending(const QueueEntry* entry) const 20611375Sandreas.hansson@arm.com { 20713861Sodanrc@yahoo.com.br for (const auto& ready_entry : readyList) { 20813861Sodanrc@yahoo.com.br if (ready_entry->conflictAddr(entry)) { 20913861Sodanrc@yahoo.com.br return ready_entry; 21011375Sandreas.hansson@arm.com } 21111375Sandreas.hansson@arm.com } 21211375Sandreas.hansson@arm.com return nullptr; 21311375Sandreas.hansson@arm.com } 21411375Sandreas.hansson@arm.com 21511375Sandreas.hansson@arm.com /** 21611375Sandreas.hansson@arm.com * Returns the WriteQueueEntry at the head of the readyList. 21711375Sandreas.hansson@arm.com * @return The next request to service. 21811375Sandreas.hansson@arm.com */ 21911375Sandreas.hansson@arm.com Entry* getNext() const 22011375Sandreas.hansson@arm.com { 22111375Sandreas.hansson@arm.com if (readyList.empty() || readyList.front()->readyTime > curTick()) { 22211484Snikos.nikoleris@arm.com return nullptr; 22311375Sandreas.hansson@arm.com } 22411375Sandreas.hansson@arm.com return readyList.front(); 22511375Sandreas.hansson@arm.com } 22611375Sandreas.hansson@arm.com 22711375Sandreas.hansson@arm.com Tick nextReadyTime() const 22811375Sandreas.hansson@arm.com { 22911375Sandreas.hansson@arm.com return readyList.empty() ? MaxTick : readyList.front()->readyTime; 23011375Sandreas.hansson@arm.com } 23111375Sandreas.hansson@arm.com 23211375Sandreas.hansson@arm.com /** 23311375Sandreas.hansson@arm.com * Removes the given entry from the queue. This places the entry 23411375Sandreas.hansson@arm.com * on the free list. 23511375Sandreas.hansson@arm.com * 23611375Sandreas.hansson@arm.com * @param entry 23711375Sandreas.hansson@arm.com */ 23811375Sandreas.hansson@arm.com void deallocate(Entry *entry) 23911375Sandreas.hansson@arm.com { 24011375Sandreas.hansson@arm.com allocatedList.erase(entry->allocIter); 24111375Sandreas.hansson@arm.com freeList.push_front(entry); 24211375Sandreas.hansson@arm.com allocated--; 24311375Sandreas.hansson@arm.com if (entry->inService) { 24411375Sandreas.hansson@arm.com _numInService--; 24511375Sandreas.hansson@arm.com } else { 24611375Sandreas.hansson@arm.com readyList.erase(entry->readyIter); 24711375Sandreas.hansson@arm.com } 24811375Sandreas.hansson@arm.com entry->deallocate(); 24911375Sandreas.hansson@arm.com if (drainState() == DrainState::Draining && allocated == 0) { 25011375Sandreas.hansson@arm.com // Notify the drain manager that we have completed 25111375Sandreas.hansson@arm.com // draining if there are no other outstanding requests in 25211375Sandreas.hansson@arm.com // this queue. 25311375Sandreas.hansson@arm.com DPRINTF(Drain, "Queue now empty, signalling drained\n"); 25411375Sandreas.hansson@arm.com signalDrainDone(); 25511375Sandreas.hansson@arm.com } 25611375Sandreas.hansson@arm.com } 25711375Sandreas.hansson@arm.com 25811375Sandreas.hansson@arm.com DrainState drain() override 25911375Sandreas.hansson@arm.com { 26011375Sandreas.hansson@arm.com return allocated == 0 ? DrainState::Drained : DrainState::Draining; 26111375Sandreas.hansson@arm.com } 26211375Sandreas.hansson@arm.com}; 26311375Sandreas.hansson@arm.com 26411375Sandreas.hansson@arm.com#endif //__MEM_CACHE_QUEUE_HH__ 265