queued.cc revision 13551
110623Smitch.hayenga@arm.com/* 211439SRekai.GonzalezAlberquilla@arm.com * Copyright (c) 2014-2015 ARM Limited 310623Smitch.hayenga@arm.com * All rights reserved 410623Smitch.hayenga@arm.com * 510623Smitch.hayenga@arm.com * The license below extends only to copyright in the software and shall 610623Smitch.hayenga@arm.com * not be construed as granting a license to any other intellectual 710623Smitch.hayenga@arm.com * property including but not limited to intellectual property relating 810623Smitch.hayenga@arm.com * to a hardware implementation of the functionality of the software 910623Smitch.hayenga@arm.com * licensed hereunder. You may use the software subject to the license 1010623Smitch.hayenga@arm.com * terms below provided that you ensure that this notice is replicated 1110623Smitch.hayenga@arm.com * unmodified and in its entirety in all distributions of the software, 1210623Smitch.hayenga@arm.com * modified or unmodified, in source code or in binary form. 1310623Smitch.hayenga@arm.com * 1410623Smitch.hayenga@arm.com * Redistribution and use in source and binary forms, with or without 1510623Smitch.hayenga@arm.com * modification, are permitted provided that the following conditions are 1610623Smitch.hayenga@arm.com * met: redistributions of source code must retain the above copyright 1710623Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer; 1810623Smitch.hayenga@arm.com * redistributions in binary form must reproduce the above copyright 1910623Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer in the 2010623Smitch.hayenga@arm.com * documentation and/or other materials provided with the distribution; 2110623Smitch.hayenga@arm.com * neither the name of the copyright holders nor the names of its 2210623Smitch.hayenga@arm.com * contributors may be used to endorse or promote products derived from 2310623Smitch.hayenga@arm.com * this software without specific prior written permission. 2410623Smitch.hayenga@arm.com * 2510623Smitch.hayenga@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2610623Smitch.hayenga@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2710623Smitch.hayenga@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2810623Smitch.hayenga@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2910623Smitch.hayenga@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3010623Smitch.hayenga@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3110623Smitch.hayenga@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3210623Smitch.hayenga@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3310623Smitch.hayenga@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3410623Smitch.hayenga@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3510623Smitch.hayenga@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3610623Smitch.hayenga@arm.com * 3710623Smitch.hayenga@arm.com * Authors: Mitch Hayenga 3810623Smitch.hayenga@arm.com */ 3910623Smitch.hayenga@arm.com 4011793Sbrandon.potter@amd.com#include "mem/cache/prefetch/queued.hh" 4111793Sbrandon.potter@amd.com 4212727Snikos.nikoleris@arm.com#include <cassert> 4312727Snikos.nikoleris@arm.com 4412727Snikos.nikoleris@arm.com#include "base/logging.hh" 4512727Snikos.nikoleris@arm.com#include "base/trace.hh" 4610623Smitch.hayenga@arm.com#include "debug/HWPrefetch.hh" 4712727Snikos.nikoleris@arm.com#include "mem/request.hh" 4812727Snikos.nikoleris@arm.com#include "params/QueuedPrefetcher.hh" 4910623Smitch.hayenga@arm.com 5010623Smitch.hayenga@arm.comQueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 5110623Smitch.hayenga@arm.com : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 5210623Smitch.hayenga@arm.com queueSquash(p->queue_squash), queueFilter(p->queue_filter), 5310623Smitch.hayenga@arm.com cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 5410623Smitch.hayenga@arm.com{ 5510623Smitch.hayenga@arm.com 5610623Smitch.hayenga@arm.com} 5710623Smitch.hayenga@arm.com 5810623Smitch.hayenga@arm.comQueuedPrefetcher::~QueuedPrefetcher() 5910623Smitch.hayenga@arm.com{ 6010623Smitch.hayenga@arm.com // Delete the queued prefetch packets 6110623Smitch.hayenga@arm.com for (DeferredPacket &p : pfq) { 6210623Smitch.hayenga@arm.com delete p.pkt; 6310623Smitch.hayenga@arm.com } 6410623Smitch.hayenga@arm.com} 6510623Smitch.hayenga@arm.com 6613416Sjavier.bueno@metempsy.comvoid 6713551Sjavier.bueno@metempsy.comQueuedPrefetcher::notify(const PacketPtr &pkt, const PrefetchInfo &pfi) 6810623Smitch.hayenga@arm.com{ 6913551Sjavier.bueno@metempsy.com Addr blk_addr = blockAddress(pfi.getAddr()); 7013551Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 7110623Smitch.hayenga@arm.com 7213551Sjavier.bueno@metempsy.com // Squash queued prefetches if demand miss to same line 7313551Sjavier.bueno@metempsy.com if (queueSquash) { 7413551Sjavier.bueno@metempsy.com auto itr = pfq.begin(); 7513551Sjavier.bueno@metempsy.com while (itr != pfq.end()) { 7613551Sjavier.bueno@metempsy.com if (itr->pfInfo.getAddr() == blk_addr && 7713551Sjavier.bueno@metempsy.com itr->pfInfo.isSecure() == is_secure) { 7813551Sjavier.bueno@metempsy.com delete itr->pkt; 7913551Sjavier.bueno@metempsy.com itr = pfq.erase(itr); 8013551Sjavier.bueno@metempsy.com } else { 8113551Sjavier.bueno@metempsy.com ++itr; 8210623Smitch.hayenga@arm.com } 8310623Smitch.hayenga@arm.com } 8413551Sjavier.bueno@metempsy.com } 8510623Smitch.hayenga@arm.com 8613551Sjavier.bueno@metempsy.com // Calculate prefetches given this access 8713551Sjavier.bueno@metempsy.com std::vector<AddrPriority> addresses; 8813551Sjavier.bueno@metempsy.com calculatePrefetch(pfi, addresses); 8910623Smitch.hayenga@arm.com 9013551Sjavier.bueno@metempsy.com // Queue up generated prefetches 9113551Sjavier.bueno@metempsy.com for (AddrPriority& addr_prio : addresses) { 9210623Smitch.hayenga@arm.com 9313551Sjavier.bueno@metempsy.com // Block align prefetch address 9413551Sjavier.bueno@metempsy.com addr_prio.first = blockAddress(addr_prio.first); 9510623Smitch.hayenga@arm.com 9613551Sjavier.bueno@metempsy.com PrefetchInfo new_pfi(pfi,addr_prio.first); 9711439SRekai.GonzalezAlberquilla@arm.com 9813551Sjavier.bueno@metempsy.com pfIdentified++; 9913551Sjavier.bueno@metempsy.com DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 10013551Sjavier.bueno@metempsy.com "inserting into prefetch queue.\n", new_pfi.getAddr()); 10113551Sjavier.bueno@metempsy.com 10213551Sjavier.bueno@metempsy.com // Create and insert the request 10313551Sjavier.bueno@metempsy.com insert(pkt, new_pfi, addr_prio.second); 10410623Smitch.hayenga@arm.com } 10510623Smitch.hayenga@arm.com} 10610623Smitch.hayenga@arm.com 10710623Smitch.hayenga@arm.comPacketPtr 10810623Smitch.hayenga@arm.comQueuedPrefetcher::getPacket() 10910623Smitch.hayenga@arm.com{ 11010623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 11110623Smitch.hayenga@arm.com 11210623Smitch.hayenga@arm.com if (pfq.empty()) { 11310623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 11411484Snikos.nikoleris@arm.com return nullptr; 11510623Smitch.hayenga@arm.com } 11610623Smitch.hayenga@arm.com 11713551Sjavier.bueno@metempsy.com PacketPtr pkt = pfq.front().pkt; 11810623Smitch.hayenga@arm.com pfq.pop_front(); 11910623Smitch.hayenga@arm.com 12010623Smitch.hayenga@arm.com pfIssued++; 12111484Snikos.nikoleris@arm.com assert(pkt != nullptr); 12210623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 12310623Smitch.hayenga@arm.com return pkt; 12410623Smitch.hayenga@arm.com} 12510623Smitch.hayenga@arm.com 12613422Sodanrc@yahoo.com.brQueuedPrefetcher::const_iterator 12713551Sjavier.bueno@metempsy.comQueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) const 12810623Smitch.hayenga@arm.com{ 12911439SRekai.GonzalezAlberquilla@arm.com for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 13013551Sjavier.bueno@metempsy.com if (dp->pfInfo.sameAddr(pfi)) return dp; 13110623Smitch.hayenga@arm.com } 13210623Smitch.hayenga@arm.com 13311439SRekai.GonzalezAlberquilla@arm.com return pfq.end(); 13411439SRekai.GonzalezAlberquilla@arm.com} 13511439SRekai.GonzalezAlberquilla@arm.com 13611439SRekai.GonzalezAlberquilla@arm.comQueuedPrefetcher::iterator 13713551Sjavier.bueno@metempsy.comQueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) 13811439SRekai.GonzalezAlberquilla@arm.com{ 13911439SRekai.GonzalezAlberquilla@arm.com for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 14013551Sjavier.bueno@metempsy.com if (dp->pfInfo.sameAddr(pfi)) return dp; 14111439SRekai.GonzalezAlberquilla@arm.com } 14211439SRekai.GonzalezAlberquilla@arm.com 14311439SRekai.GonzalezAlberquilla@arm.com return pfq.end(); 14410623Smitch.hayenga@arm.com} 14510623Smitch.hayenga@arm.com 14610623Smitch.hayenga@arm.comvoid 14710623Smitch.hayenga@arm.comQueuedPrefetcher::regStats() 14810623Smitch.hayenga@arm.com{ 14910623Smitch.hayenga@arm.com BasePrefetcher::regStats(); 15010623Smitch.hayenga@arm.com 15110623Smitch.hayenga@arm.com pfIdentified 15210623Smitch.hayenga@arm.com .name(name() + ".pfIdentified") 15310623Smitch.hayenga@arm.com .desc("number of prefetch candidates identified"); 15410623Smitch.hayenga@arm.com 15510623Smitch.hayenga@arm.com pfBufferHit 15610623Smitch.hayenga@arm.com .name(name() + ".pfBufferHit") 15710623Smitch.hayenga@arm.com .desc("number of redundant prefetches already in prefetch queue"); 15810623Smitch.hayenga@arm.com 15910623Smitch.hayenga@arm.com pfInCache 16010623Smitch.hayenga@arm.com .name(name() + ".pfInCache") 16110623Smitch.hayenga@arm.com .desc("number of redundant prefetches already in cache/mshr dropped"); 16210623Smitch.hayenga@arm.com 16310623Smitch.hayenga@arm.com pfRemovedFull 16410623Smitch.hayenga@arm.com .name(name() + ".pfRemovedFull") 16510623Smitch.hayenga@arm.com .desc("number of prefetches dropped due to prefetch queue size"); 16610623Smitch.hayenga@arm.com 16710623Smitch.hayenga@arm.com pfSpanPage 16810623Smitch.hayenga@arm.com .name(name() + ".pfSpanPage") 16910623Smitch.hayenga@arm.com .desc("number of prefetches not generated due to page crossing"); 17010623Smitch.hayenga@arm.com} 17111439SRekai.GonzalezAlberquilla@arm.com 17213551Sjavier.bueno@metempsy.comvoid 17313551Sjavier.bueno@metempsy.comQueuedPrefetcher::insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, 17413551Sjavier.bueno@metempsy.com int32_t priority) 17511439SRekai.GonzalezAlberquilla@arm.com{ 17611439SRekai.GonzalezAlberquilla@arm.com if (queueFilter) { 17713551Sjavier.bueno@metempsy.com iterator it = inPrefetch(new_pfi); 17811439SRekai.GonzalezAlberquilla@arm.com /* If the address is already in the queue, update priority and leave */ 17911439SRekai.GonzalezAlberquilla@arm.com if (it != pfq.end()) { 18011439SRekai.GonzalezAlberquilla@arm.com pfBufferHit++; 18113551Sjavier.bueno@metempsy.com if (it->priority < priority) { 18211439SRekai.GonzalezAlberquilla@arm.com /* Update priority value and position in the queue */ 18313551Sjavier.bueno@metempsy.com it->priority = priority; 18411439SRekai.GonzalezAlberquilla@arm.com iterator prev = it; 18511439SRekai.GonzalezAlberquilla@arm.com bool cont = true; 18611439SRekai.GonzalezAlberquilla@arm.com while (cont && prev != pfq.begin()) { 18711439SRekai.GonzalezAlberquilla@arm.com prev--; 18811439SRekai.GonzalezAlberquilla@arm.com /* If the packet has higher priority, swap */ 18911439SRekai.GonzalezAlberquilla@arm.com if (*it > *prev) { 19011439SRekai.GonzalezAlberquilla@arm.com std::swap(*it, *prev); 19111439SRekai.GonzalezAlberquilla@arm.com it = prev; 19211439SRekai.GonzalezAlberquilla@arm.com } 19311439SRekai.GonzalezAlberquilla@arm.com } 19411439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch addr already in " 19511439SRekai.GonzalezAlberquilla@arm.com "prefetch queue, priority updated\n"); 19611439SRekai.GonzalezAlberquilla@arm.com } else { 19711439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch addr already in " 19811439SRekai.GonzalezAlberquilla@arm.com "prefetch queue\n"); 19911439SRekai.GonzalezAlberquilla@arm.com } 20013551Sjavier.bueno@metempsy.com return; 20111439SRekai.GonzalezAlberquilla@arm.com } 20211439SRekai.GonzalezAlberquilla@arm.com } 20311439SRekai.GonzalezAlberquilla@arm.com 20413551Sjavier.bueno@metempsy.com Addr target_addr = new_pfi.getAddr(); 20513551Sjavier.bueno@metempsy.com if (useVirtualAddresses) { 20613551Sjavier.bueno@metempsy.com assert(pkt->req->hasPaddr()); 20713551Sjavier.bueno@metempsy.com //if we trained with virtual addresses, compute the phsysical address 20813551Sjavier.bueno@metempsy.com if (new_pfi.getAddr() >= pkt->req->getVaddr()) { 20913551Sjavier.bueno@metempsy.com //positive stride 21013551Sjavier.bueno@metempsy.com target_addr = pkt->req->getPaddr() + 21113551Sjavier.bueno@metempsy.com (new_pfi.getAddr() - pkt->req->getVaddr()); 21213551Sjavier.bueno@metempsy.com } else { 21313551Sjavier.bueno@metempsy.com //negative stride 21413551Sjavier.bueno@metempsy.com target_addr = pkt->req->getPaddr() - 21513551Sjavier.bueno@metempsy.com (pkt->req->getVaddr() - new_pfi.getAddr()); 21613551Sjavier.bueno@metempsy.com } 21713551Sjavier.bueno@metempsy.com } 21813551Sjavier.bueno@metempsy.com 21913551Sjavier.bueno@metempsy.com if (cacheSnoop && (inCache(target_addr, new_pfi.isSecure()) || 22013551Sjavier.bueno@metempsy.com inMissQueue(target_addr, new_pfi.isSecure()))) { 22111439SRekai.GonzalezAlberquilla@arm.com pfInCache++; 22211439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Dropping redundant in " 22313551Sjavier.bueno@metempsy.com "cache/MSHR prefetch addr:%#x\n", target_addr); 22413551Sjavier.bueno@metempsy.com return; 22511439SRekai.GonzalezAlberquilla@arm.com } 22611439SRekai.GonzalezAlberquilla@arm.com 22711439SRekai.GonzalezAlberquilla@arm.com /* Create a prefetch memory request */ 22812748Sgiacomo.travaglini@arm.com RequestPtr pf_req = 22913551Sjavier.bueno@metempsy.com std::make_shared<Request>(target_addr, blkSize, 0, masterId); 23011439SRekai.GonzalezAlberquilla@arm.com 23113551Sjavier.bueno@metempsy.com if (new_pfi.isSecure()) { 23211439SRekai.GonzalezAlberquilla@arm.com pf_req->setFlags(Request::SECURE); 23311439SRekai.GonzalezAlberquilla@arm.com } 23411439SRekai.GonzalezAlberquilla@arm.com pf_req->taskId(ContextSwitchTaskId::Prefetcher); 23511439SRekai.GonzalezAlberquilla@arm.com PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 23611439SRekai.GonzalezAlberquilla@arm.com pf_pkt->allocate(); 23713551Sjavier.bueno@metempsy.com if (tagPrefetch && new_pfi.hasPC()) { 23813551Sjavier.bueno@metempsy.com // Tag prefetch packet with accessing pc 23913551Sjavier.bueno@metempsy.com pf_pkt->req->setPC(new_pfi.getPC()); 24013551Sjavier.bueno@metempsy.com } 24111439SRekai.GonzalezAlberquilla@arm.com 24211439SRekai.GonzalezAlberquilla@arm.com /* Verify prefetch buffer space for request */ 24311439SRekai.GonzalezAlberquilla@arm.com if (pfq.size() == queueSize) { 24411439SRekai.GonzalezAlberquilla@arm.com pfRemovedFull++; 24511439SRekai.GonzalezAlberquilla@arm.com /* Lowest priority packet */ 24611439SRekai.GonzalezAlberquilla@arm.com iterator it = pfq.end(); 24711439SRekai.GonzalezAlberquilla@arm.com panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 24811439SRekai.GonzalezAlberquilla@arm.com --it; 24911439SRekai.GonzalezAlberquilla@arm.com /* Look for oldest in that level of priority */ 25011439SRekai.GonzalezAlberquilla@arm.com panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 25111439SRekai.GonzalezAlberquilla@arm.com iterator prev = it; 25211439SRekai.GonzalezAlberquilla@arm.com bool cont = true; 25311439SRekai.GonzalezAlberquilla@arm.com /* While not at the head of the queue */ 25411439SRekai.GonzalezAlberquilla@arm.com while (cont && prev != pfq.begin()) { 25511439SRekai.GonzalezAlberquilla@arm.com prev--; 25611439SRekai.GonzalezAlberquilla@arm.com /* While at the same level of priority */ 25713551Sjavier.bueno@metempsy.com cont = prev->priority == it->priority; 25811439SRekai.GonzalezAlberquilla@arm.com if (cont) 25911439SRekai.GonzalezAlberquilla@arm.com /* update pointer */ 26011439SRekai.GonzalezAlberquilla@arm.com it = prev; 26111439SRekai.GonzalezAlberquilla@arm.com } 26211439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 26313551Sjavier.bueno@metempsy.com "oldest packet, addr: %#x", it->pfInfo.getAddr()); 26411439SRekai.GonzalezAlberquilla@arm.com delete it->pkt; 26511439SRekai.GonzalezAlberquilla@arm.com pfq.erase(it); 26611439SRekai.GonzalezAlberquilla@arm.com } 26711439SRekai.GonzalezAlberquilla@arm.com 26811439SRekai.GonzalezAlberquilla@arm.com Tick pf_time = curTick() + clockPeriod() * latency; 26911439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch queued. " 27011439SRekai.GonzalezAlberquilla@arm.com "addr:%#x priority: %3d tick:%lld.\n", 27113551Sjavier.bueno@metempsy.com target_addr, priority, pf_time); 27211439SRekai.GonzalezAlberquilla@arm.com 27311439SRekai.GonzalezAlberquilla@arm.com /* Create the packet and find the spot to insert it */ 27413551Sjavier.bueno@metempsy.com DeferredPacket dpp(new_pfi, pf_time, pf_pkt, priority); 27511439SRekai.GonzalezAlberquilla@arm.com if (pfq.size() == 0) { 27611439SRekai.GonzalezAlberquilla@arm.com pfq.emplace_back(dpp); 27711439SRekai.GonzalezAlberquilla@arm.com } else { 27811439SRekai.GonzalezAlberquilla@arm.com iterator it = pfq.end(); 27913428Sjavier.bueno@metempsy.com do { 28011439SRekai.GonzalezAlberquilla@arm.com --it; 28113428Sjavier.bueno@metempsy.com } while (it != pfq.begin() && dpp > *it); 28211439SRekai.GonzalezAlberquilla@arm.com /* If we reach the head, we have to see if the new element is new head 28311439SRekai.GonzalezAlberquilla@arm.com * or not */ 28411439SRekai.GonzalezAlberquilla@arm.com if (it == pfq.begin() && dpp <= *it) 28511439SRekai.GonzalezAlberquilla@arm.com it++; 28611439SRekai.GonzalezAlberquilla@arm.com pfq.insert(it, dpp); 28711439SRekai.GonzalezAlberquilla@arm.com } 28811439SRekai.GonzalezAlberquilla@arm.com} 289