src/mem/cache/prefetch/base.cc

   1 /*
   2  * Copyright (c) 2013 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  * Copyright (c) 2005 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Ron Dreslinski
  41  */
  42
  43 /**
  44  * @file
  45  * Hardware Prefetcher Definition.
  46  */
  47
  48 #include <list>
  49
  50 #include "arch/isa_traits.hh"
  51 #include "base/trace.hh"
  52 #include "config/the_isa.hh"
  53 #include "debug/HWPrefetch.hh"
  54 #include "mem/cache/prefetch/base.hh"
  55 #include "mem/cache/base.hh"
  56 #include "mem/request.hh"
  57 #include "sim/system.hh"
  58
  59 BasePrefetcher::BasePrefetcher(const Params *p)
  60     : ClockedObject(p), size(p->size), cache(nullptr), blkSize(0),
  61       latency(p->latency), degree(p->degree),
  62       useMasterId(p->use_master_id), pageStop(!p->cross_pages),
  63       serialSquash(p->serial_squash), onlyData(p->data_accesses_only),
  64       onMissOnly(p->on_miss_only), onReadOnly(p->on_read_only),
  65       onPrefetch(p->on_prefetch), system(p->sys),
  66       masterId(system->getMasterId(name()))
  67 {
  68 }
  69
  70 void
  71 BasePrefetcher::setCache(BaseCache *_cache)
  72 {
  73     assert(!cache);
  74     cache = _cache;
  75     blkSize = cache->getBlockSize();
  76 }
  77
  78 void
  79 BasePrefetcher::regStats()
  80 {
  81     pfIdentified
  82         .name(name() + ".prefetcher.num_hwpf_identified")
  83         .desc("number of hwpf identified")
  84         ;
  85
  86     pfMSHRHit
  87         .name(name() + ".prefetcher.num_hwpf_already_in_mshr")
  88         .desc("number of hwpf that were already in mshr")
  89         ;
  90
  91     pfCacheHit
  92         .name(name() + ".prefetcher.num_hwpf_already_in_cache")
  93         .desc("number of hwpf that were already in the cache")
  94         ;
  95
  96     pfBufferHit
  97         .name(name() + ".prefetcher.num_hwpf_already_in_prefetcher")
  98         .desc("number of hwpf that were already in the prefetch queue")
  99         ;
 100
 101     pfRemovedFull
 102         .name(name() + ".prefetcher.num_hwpf_evicted")
 103         .desc("number of hwpf removed due to no buffer left")
 104         ;
 105
 106     pfRemovedMSHR
 107         .name(name() + ".prefetcher.num_hwpf_removed_MSHR_hit")
 108         .desc("number of hwpf removed because MSHR allocated")
 109         ;
 110
 111     pfIssued
 112         .name(name() + ".prefetcher.num_hwpf_issued")
 113         .desc("number of hwpf issued")
 114         ;
 115
 116     pfSpanPage
 117         .name(name() + ".prefetcher.num_hwpf_span_page")
 118         .desc("number of hwpf spanning a virtual page")
 119         ;
 120
 121     pfSquashed
 122         .name(name() + ".prefetcher.num_hwpf_squashed_from_miss")
 123         .desc("number of hwpf that got squashed due to a miss "
 124               "aborting calculation time")
 125         ;
 126 }
 127
 128 inline bool
 129 BasePrefetcher::inCache(Addr addr, bool is_secure)
 130 {
 131     if (cache->inCache(addr, is_secure)) {
 132         pfCacheHit++;
 133         return true;
 134     }
 135     return false;
 136 }
 137
 138 inline bool
 139 BasePrefetcher::inMissQueue(Addr addr, bool is_secure)
 140 {
 141     if (cache->inMissQueue(addr, is_secure)) {
 142         pfMSHRHit++;
 143         return true;
 144     }
 145     return false;
 146 }
 147
 148 PacketPtr
 149 BasePrefetcher::getPacket()
 150 {
 151     DPRINTF(HWPrefetch, "Requesting a hw_pf to issue\n");
 152
 153     if (pf.empty()) {
 154         DPRINTF(HWPrefetch, "No HW_PF found\n");
 155         return NULL;
 156     }
 157
 158     PacketPtr pkt = pf.begin()->pkt;
 159     while (!pf.empty()) {
 160         pkt = pf.begin()->pkt;
 161         pf.pop_front();
 162
 163         Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize-1);
 164         bool is_secure = pkt->isSecure();
 165
 166         if (!inCache(blk_addr, is_secure) && !inMissQueue(blk_addr, is_secure))
 167             // we found a prefetch, return it
 168             break;
 169
 170         DPRINTF(HWPrefetch, "addr 0x%x (%s) in cache, skipping\n",
 171                 pkt->getAddr(), is_secure ? "s" : "ns");
 172         delete pkt->req;
 173         delete pkt;
 174
 175         if (pf.empty()) {
 176             cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 177             return NULL; // None left, all were in cache
 178         }
 179     }
 180
 181     pfIssued++;
 182     assert(pkt != NULL);
 183     DPRINTF(HWPrefetch, "returning 0x%x (%s)\n", pkt->getAddr(),
 184             pkt->isSecure() ? "s" : "ns");
 185     return pkt;
 186 }
 187
 188
 189 Tick
 190 BasePrefetcher::notify(PacketPtr &pkt, Tick tick)
 191 {
 192     // Don't consult the prefetcher if any of the following conditons are true
 193     // 1) The request is uncacheable
 194     // 2) The request is a fetch, but we are only prefeching data
 195     // 3) The request is a cache hit, but we are only training on misses
 196     // 4) THe request is a write, but we are only training on reads
 197     if (!pkt->req->isUncacheable() && !(pkt->req->isInstFetch() && onlyData) &&
 198         !(onMissOnly && inCache(pkt->getAddr(), true)) &&
 199         !(onReadOnly && !pkt->isRead())) {
 200         // Calculate the blk address
 201         Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize-1);
 202         bool is_secure = pkt->isSecure();
 203
 204         // Check if miss is in pfq, if so remove it
 205         std::list<DeferredPacket>::iterator iter = inPrefetch(blk_addr,
 206                                                               is_secure);
 207         if (iter != pf.end()) {
 208             DPRINTF(HWPrefetch, "Saw a miss to a queued prefetch addr: "
 209                     "0x%x (%s), removing it\n", blk_addr,
 210                     is_secure ? "s" : "ns");
 211             pfRemovedMSHR++;
 212             delete iter->pkt->req;
 213             delete iter->pkt;
 214             iter = pf.erase(iter);
 215             if (pf.empty())
 216                 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 217         }
 218
 219         // Remove anything in queue with delay older than time
 220         // since everything is inserted in time order, start from end
 221         // and work until pf.empty() or time is earlier
 222         // This is done to emulate Aborting the previous work on a new miss
 223         // Needed for serial calculators like GHB
 224         if (serialSquash) {
 225             iter = pf.end();
 226             if (iter != pf.begin())
 227                 iter--;
 228             while (!pf.empty() && iter->tick >= tick) {
 229                 pfSquashed++;
 230                 DPRINTF(HWPrefetch, "Squashing old prefetch addr: 0x%x\n",
 231                         iter->pkt->getAddr());
 232                 delete iter->pkt->req;
 233                 delete iter->pkt;
 234                 iter = pf.erase(iter);
 235                 if (iter != pf.begin())
 236                     iter--;
 237             }
 238             if (pf.empty())
 239                 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 240         }
 241
 242
 243         std::list<Addr> addresses;
 244         std::list<Cycles> delays;
 245         calculatePrefetch(pkt, addresses, delays);
 246
 247         std::list<Addr>::iterator addrIter = addresses.begin();
 248         std::list<Cycles>::iterator delayIter = delays.begin();
 249         for (; addrIter != addresses.end(); ++addrIter, ++delayIter) {
 250             Addr addr = *addrIter;
 251
 252             pfIdentified++;
 253
 254             DPRINTF(HWPrefetch, "Found a pf candidate addr: 0x%x, "
 255                     "inserting into prefetch queue with delay %d time %d\n",
 256                     addr, *delayIter, time);
 257
 258             // Check if it is already in the pf buffer
 259             if (inPrefetch(addr, is_secure) != pf.end()) {
 260                 pfBufferHit++;
 261                 DPRINTF(HWPrefetch, "Prefetch addr already in pf buffer\n");
 262                 continue;
 263             }
 264
 265             // create a prefetch memreq
 266             Request *prefetchReq = new Request(*addrIter, blkSize, 0, masterId);
 267             if (is_secure)
 268                 prefetchReq->setFlags(Request::SECURE);
 269             prefetchReq->taskId(ContextSwitchTaskId::Prefetcher);
 270             PacketPtr prefetch =
 271                 new Packet(prefetchReq, MemCmd::HardPFReq);
 272             prefetch->allocate();
 273             prefetch->req->setThreadContext(pkt->req->contextId(),
 274                                             pkt->req->threadId());
 275
 276             // Tag orefetch reqeuests with corresponding PC to train lower
 277             // cache-level prefetchers
 278             if (onPrefetch && pkt->req->hasPC())
 279                 prefetch->req->setPC(pkt->req->getPC());
 280
 281             // We just remove the head if we are full
 282             if (pf.size() == size) {
 283                 pfRemovedFull++;
 284                 PacketPtr old_pkt = pf.begin()->pkt;
 285                 DPRINTF(HWPrefetch, "Prefetch queue full, "
 286                         "removing oldest 0x%x\n", old_pkt->getAddr());
 287                 delete old_pkt->req;
 288                 delete old_pkt;
 289                 pf.pop_front();
 290             }
 291
 292             pf.push_back(DeferredPacket(tick + clockPeriod() * *delayIter,
 293                                         prefetch));
 294         }
 295     }
 296
 297     return pf.empty() ? 0 : pf.front().tick;
 298 }
 299
 300 std::list<BasePrefetcher::DeferredPacket>::iterator
 301 BasePrefetcher::inPrefetch(Addr address, bool is_secure)
 302 {
 303     // Guaranteed to only be one match, we always check before inserting
 304     std::list<DeferredPacket>::iterator iter;
 305     for (iter = pf.begin(); iter != pf.end(); iter++) {
 306         if (((*iter).pkt->getAddr() & ~(Addr)(blkSize-1)) == address &&
 307             (*iter).pkt->isSecure() == is_secure) {
 308             return iter;
 309         }
 310     }
 311     return pf.end();
 312 }
 313
 314 bool
 315 BasePrefetcher::samePage(Addr a, Addr b)
 316 {
 317     return roundDown(a, TheISA::PageBytes) == roundDown(b, TheISA::PageBytes);
 318 }
 319
 320