queued.cc revision 14013:aeb3ca1762bb
1/* 2 * Copyright (c) 2014-2015 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Mitch Hayenga 38 */ 39 40#include "mem/cache/prefetch/queued.hh" 41 42#include <cassert> 43 44#include "arch/generic/tlb.hh" 45#include "base/logging.hh" 46#include "base/trace.hh" 47#include "debug/HWPrefetch.hh" 48#include "mem/cache/base.hh" 49#include "mem/request.hh" 50#include "params/QueuedPrefetcher.hh" 51 52void 53QueuedPrefetcher::DeferredPacket::createPkt(Addr paddr, unsigned blk_size, 54 MasterID mid, bool tag_prefetch, 55 Tick t) { 56 /* Create a prefetch memory request */ 57 RequestPtr req = std::make_shared<Request>(paddr, blk_size, 0, mid); 58 59 if (pfInfo.isSecure()) { 60 req->setFlags(Request::SECURE); 61 } 62 req->taskId(ContextSwitchTaskId::Prefetcher); 63 pkt = new Packet(req, MemCmd::HardPFReq); 64 pkt->allocate(); 65 if (tag_prefetch && pfInfo.hasPC()) { 66 // Tag prefetch packet with accessing pc 67 pkt->req->setPC(pfInfo.getPC()); 68 } 69 tick = t; 70} 71 72void 73QueuedPrefetcher::DeferredPacket::startTranslation(BaseTLB *tlb) 74{ 75 assert(translationRequest != nullptr); 76 if (!ongoingTranslation) { 77 ongoingTranslation = true; 78 // Prefetchers only operate in Timing mode 79 tlb->translateTiming(translationRequest, tc, this, BaseTLB::Read); 80 } 81} 82 83void 84QueuedPrefetcher::DeferredPacket::finish(const Fault &fault, 85 const RequestPtr &req, ThreadContext *tc, BaseTLB::Mode mode) 86{ 87 assert(ongoingTranslation); 88 ongoingTranslation = false; 89 bool failed = (fault != NoFault); 90 owner->translationComplete(this, failed); 91} 92 93QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 94 : BasePrefetcher(p), queueSize(p->queue_size), 95 missingTranslationQueueSize( 96 p->max_prefetch_requests_with_pending_translation), 97 latency(p->latency), queueSquash(p->queue_squash), 98 queueFilter(p->queue_filter), cacheSnoop(p->cache_snoop), 99 tagPrefetch(p->tag_prefetch) 100{ 101} 102 103QueuedPrefetcher::~QueuedPrefetcher() 104{ 105 // Delete the queued prefetch packets 106 for (DeferredPacket &p : pfq) { 107 delete p.pkt; 108 } 109} 110 111void 112QueuedPrefetcher::notify(const PacketPtr &pkt, const PrefetchInfo &pfi) 113{ 114 Addr blk_addr = blockAddress(pfi.getAddr()); 115 bool is_secure = pfi.isSecure(); 116 117 // Squash queued prefetches if demand miss to same line 118 if (queueSquash) { 119 auto itr = pfq.begin(); 120 while (itr != pfq.end()) { 121 if (itr->pfInfo.getAddr() == blk_addr && 122 itr->pfInfo.isSecure() == is_secure) { 123 delete itr->pkt; 124 itr = pfq.erase(itr); 125 } else { 126 ++itr; 127 } 128 } 129 } 130 131 // Calculate prefetches given this access 132 std::vector<AddrPriority> addresses; 133 calculatePrefetch(pfi, addresses); 134 135 // Queue up generated prefetches 136 for (AddrPriority& addr_prio : addresses) { 137 138 // Block align prefetch address 139 addr_prio.first = blockAddress(addr_prio.first); 140 141 if (!samePage(addr_prio.first, pfi.getAddr())) { 142 pfSpanPage += 1; 143 } 144 145 bool can_cross_page = (tlb != nullptr); 146 if (can_cross_page || samePage(addr_prio.first, pfi.getAddr())) { 147 PrefetchInfo new_pfi(pfi,addr_prio.first); 148 pfIdentified++; 149 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 150 "inserting into prefetch queue.\n", new_pfi.getAddr()); 151 // Create and insert the request 152 insert(pkt, new_pfi, addr_prio.second); 153 } else { 154 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 155 } 156 } 157} 158 159PacketPtr 160QueuedPrefetcher::getPacket() 161{ 162 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 163 164 if (pfq.empty()) { 165 // If the queue is empty, attempt first to fill it with requests 166 // from the queue of missing translations 167 processMissingTranslations(queueSize); 168 } 169 170 if (pfq.empty()) { 171 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 172 return nullptr; 173 } 174 175 PacketPtr pkt = pfq.front().pkt; 176 pfq.pop_front(); 177 178 pfIssued++; 179 issuedPrefetches += 1; 180 assert(pkt != nullptr); 181 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 182 183 processMissingTranslations(queueSize - pfq.size()); 184 return pkt; 185} 186 187void 188QueuedPrefetcher::regStats() 189{ 190 BasePrefetcher::regStats(); 191 192 pfIdentified 193 .name(name() + ".pfIdentified") 194 .desc("number of prefetch candidates identified"); 195 196 pfBufferHit 197 .name(name() + ".pfBufferHit") 198 .desc("number of redundant prefetches already in prefetch queue"); 199 200 pfInCache 201 .name(name() + ".pfInCache") 202 .desc("number of redundant prefetches already in cache/mshr dropped"); 203 204 pfRemovedFull 205 .name(name() + ".pfRemovedFull") 206 .desc("number of prefetches dropped due to prefetch queue size"); 207 208 pfSpanPage 209 .name(name() + ".pfSpanPage") 210 .desc("number of prefetches that crossed the page"); 211} 212 213 214void 215QueuedPrefetcher::processMissingTranslations(unsigned max) 216{ 217 unsigned count = 0; 218 iterator it = pfqMissingTranslation.begin(); 219 while (it != pfqMissingTranslation.end() && count < max) { 220 DeferredPacket &dp = *it; 221 // Increase the iterator first because dp.startTranslation can end up 222 // calling finishTranslation, which will erase "it" 223 it++; 224 dp.startTranslation(tlb); 225 count += 1; 226 } 227} 228 229void 230QueuedPrefetcher::translationComplete(DeferredPacket *dp, bool failed) 231{ 232 auto it = pfqMissingTranslation.begin(); 233 while (it != pfqMissingTranslation.end()) { 234 if (&(*it) == dp) { 235 break; 236 } 237 it++; 238 } 239 assert(it != pfqMissingTranslation.end()); 240 if (!failed) { 241 DPRINTF(HWPrefetch, "%s Translation of vaddr %#x succeeded: " 242 "paddr %#x \n", tlb->name(), 243 it->translationRequest->getVaddr(), 244 it->translationRequest->getPaddr()); 245 Addr target_paddr = it->translationRequest->getPaddr(); 246 // check if this prefetch is already redundant 247 if (cacheSnoop && (inCache(target_paddr, it->pfInfo.isSecure()) || 248 inMissQueue(target_paddr, it->pfInfo.isSecure()))) { 249 pfInCache++; 250 DPRINTF(HWPrefetch, "Dropping redundant in " 251 "cache/MSHR prefetch addr:%#x\n", target_paddr); 252 } else { 253 Tick pf_time = curTick() + clockPeriod() * latency; 254 it->createPkt(it->translationRequest->getPaddr(), blkSize, 255 masterId, tagPrefetch, pf_time); 256 addToQueue(pfq, *it); 257 } 258 } else { 259 DPRINTF(HWPrefetch, "%s Translation of vaddr %#x failed, dropping " 260 "prefetch request %#x \n", tlb->name(), 261 it->translationRequest->getVaddr()); 262 } 263 pfqMissingTranslation.erase(it); 264} 265 266bool 267QueuedPrefetcher::alreadyInQueue(std::list<DeferredPacket> &queue, 268 const PrefetchInfo &pfi, int32_t priority) 269{ 270 bool found = false; 271 iterator it; 272 for (it = queue.begin(); it != queue.end() && !found; it++) { 273 found = it->pfInfo.sameAddr(pfi); 274 } 275 276 /* If the address is already in the queue, update priority and leave */ 277 if (it != queue.end()) { 278 pfBufferHit++; 279 if (it->priority < priority) { 280 /* Update priority value and position in the queue */ 281 it->priority = priority; 282 iterator prev = it; 283 while (prev != queue.begin()) { 284 prev--; 285 /* If the packet has higher priority, swap */ 286 if (*it > *prev) { 287 std::swap(*it, *prev); 288 it = prev; 289 } 290 } 291 DPRINTF(HWPrefetch, "Prefetch addr already in " 292 "prefetch queue, priority updated\n"); 293 } else { 294 DPRINTF(HWPrefetch, "Prefetch addr already in " 295 "prefetch queue\n"); 296 } 297 } 298 return found; 299} 300 301RequestPtr 302QueuedPrefetcher::createPrefetchRequest(Addr addr, PrefetchInfo const &pfi, 303 PacketPtr pkt) 304{ 305 RequestPtr translation_req = std::make_shared<Request>(pkt->req->getAsid(), 306 addr, blkSize, pkt->req->getFlags(), masterId, pfi.getPC(), 307 pkt->req->contextId()); 308 translation_req->setFlags(Request::PREFETCH); 309 return translation_req; 310} 311 312void 313QueuedPrefetcher::insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, 314 int32_t priority) 315{ 316 if (queueFilter) { 317 if (alreadyInQueue(pfq, new_pfi, priority)) { 318 return; 319 } 320 if (alreadyInQueue(pfqMissingTranslation, new_pfi, priority)) { 321 return; 322 } 323 } 324 325 /* 326 * Physical address computation 327 * if the prefetch is within the same page 328 * using VA: add the computed stride to the original PA 329 * using PA: no actions needed 330 * if we are page crossing 331 * using VA: Create a translaion request and enqueue the corresponding 332 * deferred packet to the queue of pending translations 333 * using PA: use the provided VA to obtain the target VA, then attempt to 334 * translate the resulting address 335 */ 336 337 Addr orig_addr = useVirtualAddresses ? 338 pkt->req->getVaddr() : pkt->req->getPaddr(); 339 bool positive_stride = new_pfi.getAddr() >= orig_addr; 340 Addr stride = positive_stride ? 341 (new_pfi.getAddr() - orig_addr) : (orig_addr - new_pfi.getAddr()); 342 343 Addr target_paddr; 344 bool has_target_pa = false; 345 RequestPtr translation_req = nullptr; 346 if (samePage(orig_addr, new_pfi.getAddr())) { 347 if (useVirtualAddresses) { 348 // if we trained with virtual addresses, 349 // compute the target PA using the original PA and adding the 350 // prefetch stride (difference between target VA and original VA) 351 target_paddr = positive_stride ? (pkt->req->getPaddr() + stride) : 352 (pkt->req->getPaddr() - stride); 353 } else { 354 target_paddr = new_pfi.getAddr(); 355 } 356 has_target_pa = true; 357 } else { 358 // Page crossing reference 359 360 // ContextID is needed for translation 361 if (!pkt->req->hasContextId()) { 362 return; 363 } 364 if (useVirtualAddresses) { 365 has_target_pa = false; 366 translation_req = createPrefetchRequest(new_pfi.getAddr(), new_pfi, 367 pkt); 368 } else if (pkt->req->hasVaddr()) { 369 has_target_pa = false; 370 // Compute the target VA using req->getVaddr + stride 371 Addr target_vaddr = positive_stride ? 372 (pkt->req->getVaddr() + stride) : 373 (pkt->req->getVaddr() - stride); 374 translation_req = createPrefetchRequest(target_vaddr, new_pfi, 375 pkt); 376 } else { 377 // Using PA for training but the request does not have a VA, 378 // unable to process this page crossing prefetch. 379 return; 380 } 381 } 382 if (has_target_pa && cacheSnoop && 383 (inCache(target_paddr, new_pfi.isSecure()) || 384 inMissQueue(target_paddr, new_pfi.isSecure()))) { 385 pfInCache++; 386 DPRINTF(HWPrefetch, "Dropping redundant in " 387 "cache/MSHR prefetch addr:%#x\n", target_paddr); 388 return; 389 } 390 391 /* Create the packet and find the spot to insert it */ 392 DeferredPacket dpp(this, new_pfi, 0, priority); 393 if (has_target_pa) { 394 Tick pf_time = curTick() + clockPeriod() * latency; 395 dpp.createPkt(target_paddr, blkSize, masterId, tagPrefetch, pf_time); 396 DPRINTF(HWPrefetch, "Prefetch queued. " 397 "addr:%#x priority: %3d tick:%lld.\n", 398 new_pfi.getAddr(), priority, pf_time); 399 addToQueue(pfq, dpp); 400 } else { 401 // Add the translation request and try to resolve it later 402 dpp.setTranslationRequest(translation_req); 403 dpp.tc = cache->system->getThreadContext(translation_req->contextId()); 404 DPRINTF(HWPrefetch, "Prefetch queued with no translation. " 405 "addr:%#x priority: %3d\n", new_pfi.getAddr(), priority); 406 addToQueue(pfqMissingTranslation, dpp); 407 } 408} 409 410void 411QueuedPrefetcher::addToQueue(std::list<DeferredPacket> &queue, 412 DeferredPacket &dpp) 413{ 414 /* Verify prefetch buffer space for request */ 415 if (queue.size() == queueSize) { 416 pfRemovedFull++; 417 /* Lowest priority packet */ 418 iterator it = queue.end(); 419 panic_if (it == queue.begin(), 420 "Prefetch queue is both full and empty!"); 421 --it; 422 /* Look for oldest in that level of priority */ 423 panic_if (it == queue.begin(), 424 "Prefetch queue is full with 1 element!"); 425 iterator prev = it; 426 bool cont = true; 427 /* While not at the head of the queue */ 428 while (cont && prev != queue.begin()) { 429 prev--; 430 /* While at the same level of priority */ 431 cont = prev->priority == it->priority; 432 if (cont) 433 /* update pointer */ 434 it = prev; 435 } 436 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 437 "oldest packet, addr: %#x\n",it->pfInfo.getAddr()); 438 delete it->pkt; 439 queue.erase(it); 440 } 441 442 if (queue.size() == 0) { 443 queue.emplace_back(dpp); 444 } else { 445 iterator it = queue.end(); 446 do { 447 --it; 448 } while (it != queue.begin() && dpp > *it); 449 /* If we reach the head, we have to see if the new element is new head 450 * or not */ 451 if (it == queue.begin() && dpp <= *it) 452 it++; 453 queue.insert(it, dpp); 454 } 455} 456