gem5  v20.1.0.0
fa_lru.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012-2013,2016,2018 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) 2003-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 
46 #ifndef __MEM_CACHE_TAGS_FA_LRU_HH__
47 #define __MEM_CACHE_TAGS_FA_LRU_HH__
48 
49 #include <cstdint>
50 #include <functional>
51 #include <string>
52 #include <unordered_map>
53 #include <vector>
54 
55 #include "base/bitfield.hh"
56 #include "base/intmath.hh"
57 #include "base/logging.hh"
58 #include "base/statistics.hh"
59 #include "base/types.hh"
60 #include "mem/cache/cache_blk.hh"
61 #include "mem/cache/tags/base.hh"
62 #include "mem/packet.hh"
63 #include "params/FALRU.hh"
64 
65 // Uncomment to enable sanity checks for the FALRU cache and the
66 // TrackedCaches class
67 //#define FALRU_DEBUG
68 
69 class BaseCache;
71 
72 // A bitmask of the caches we are keeping track of. Currently the
73 // lowest bit is the smallest cache we are tracking, as it is
74 // specified by the corresponding parameter. The rest of the bits are
75 // for exponentially growing cache sizes.
76 typedef uint32_t CachesMask;
77 
81 class FALRUBlk : public CacheBlk
82 {
83  public:
84  FALRUBlk() : CacheBlk(), prev(nullptr), next(nullptr), inCachesMask(0) {}
85 
90 
93 
99  std::string print() const override;
100 };
101 
106 class FALRU : public BaseTags
107 {
108  public:
110  typedef FALRUBlk BlkType;
111 
112  protected:
115 
120 
122  struct PairHash
123  {
124  template <class T1, class T2>
125  std::size_t operator()(const std::pair<T1, T2> &p) const
126  {
127  return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second);
128  }
129  };
131  typedef std::unordered_map<TagHashKey, FALRUBlk *, PairHash> TagHash;
132 
135 
141  void moveToHead(FALRUBlk *blk);
142 
148  void moveToTail(FALRUBlk *blk);
149 
150  public:
151  typedef FALRUParams Params;
152 
156  FALRU(const Params *p);
157  ~FALRU();
158 
162  void tagsInit() override;
163 
167  void regStats() override;
168 
173  void invalidate(CacheBlk *blk) override;
174 
187  CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
188  CachesMask *in_cache_mask);
189 
193  CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override;
194 
202  CacheBlk* findBlock(Addr addr, bool is_secure) const override;
203 
211  ReplaceableEntry* findBlockBySetAndWay(int set, int way) const override;
212 
223  CacheBlk* findVictim(Addr addr, const bool is_secure,
224  const std::size_t size,
225  std::vector<CacheBlk*>& evict_blks) override;
226 
233  void insertBlock(const PacketPtr pkt, CacheBlk *blk) override;
234 
241  Addr extractTag(Addr addr) const override
242  {
243  return blkAlign(addr);
244  }
245 
252  Addr regenerateBlkAddr(const CacheBlk* blk) const override
253  {
254  return blk->tag;
255  }
256 
257  void forEachBlk(std::function<void(CacheBlk &)> visitor) override {
258  for (int i = 0; i < numBlocks; i++) {
259  visitor(blks[i]);
260  }
261  }
262 
263  bool anyBlk(std::function<bool(CacheBlk &)> visitor) override {
264  for (int i = 0; i < numBlocks; i++) {
265  if (visitor(blks[i])) {
266  return true;
267  }
268  }
269  return false;
270  }
271 
272  private:
280  {
281  public:
282  CacheTracking(unsigned min_size, unsigned max_size,
283  unsigned block_size)
284  : blkSize(block_size),
285  minTrackedSize(min_size),
286  numTrackedCaches(max_size > min_size ?
287  floorLog2(max_size) - floorLog2(min_size) : 0),
290  {
291  fatal_if(numTrackedCaches > sizeof(CachesMask) * 8,
292  "Not enough bits (%s) in type CachesMask type to keep "
293  "track of %d caches\n", sizeof(CachesMask),
295  }
296 
305  void init(FALRUBlk *head, FALRUBlk *tail);
306 
316  void moveBlockToHead(FALRUBlk *blk);
317 
327  void moveBlockToTail(FALRUBlk *blk);
328 
339  void recordAccess(FALRUBlk *blk);
340 
351  void check(const FALRUBlk *head, const FALRUBlk *tail) const;
352 
356  void regStats(std::string name);
357 
358  private:
360  const unsigned blkSize;
362  const unsigned minTrackedSize;
364  const int numTrackedCaches;
369 
370  protected:
384 
388  };
390 };
391 
392 #endif // __MEM_CACHE_TAGS_FA_LRU_HH__
FALRU::CacheTracking::numTrackedCaches
const int numTrackedCaches
The number of different size caches being tracked.
Definition: fa_lru.hh:364
ReplaceableEntry
A replaceable entry is a basic entry in a 2d table-like structure that needs to have replacement func...
Definition: replaceable_entry.hh:53
FALRU::cacheTracking
CacheTracking cacheTracking
Definition: fa_lru.hh:389
FALRU::head
FALRUBlk * head
The MRU block.
Definition: fa_lru.hh:117
FALRUBlk::next
FALRUBlk * next
The next block in LRU order.
Definition: fa_lru.hh:89
FALRUBlk::print
std::string print() const override
Pretty-print inCachesMask and other CacheBlk information.
Definition: fa_lru.cc:58
FALRU::CacheTracking::minTrackedSize
const unsigned minTrackedSize
The smallest cache we are tracking.
Definition: fa_lru.hh:362
BaseTags::numBlocks
const unsigned numBlocks
the number of blocks in the cache
Definition: base.hh:97
FALRU::BlkType
FALRUBlk BlkType
Typedef the block type used in this class.
Definition: fa_lru.hh:110
FALRU::TagHashKey
std::pair< Addr, bool > TagHashKey
Definition: fa_lru.hh:130
FALRU::CacheTracking::recordAccess
void recordAccess(FALRUBlk *blk)
Notify of a block access.
Definition: fa_lru.cc:395
FALRUBlk::inCachesMask
CachesMask inCachesMask
A bit mask of the caches that fit this block.
Definition: fa_lru.hh:92
FALRUBlk::FALRUBlk
FALRUBlk()
Definition: fa_lru.hh:84
FALRU::accessBlock
CacheBlk * accessBlock(Addr addr, bool is_secure, Cycles &lat, CachesMask *in_cache_mask)
Access block and update replacement data.
Definition: fa_lru.cc:143
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
FALRU::CacheTracking::misses
Stats::Vector misses
Misses in each cache.
Definition: fa_lru.hh:381
FALRU::tail
FALRUBlk * tail
The LRU block.
Definition: fa_lru.hh:119
FALRU::CacheTracking::regStats
void regStats(std::string name)
Register the stats for this object.
Definition: fa_lru.cc:428
FALRU::CacheTracking::CacheTracking
CacheTracking(unsigned min_size, unsigned max_size, unsigned block_size)
Definition: fa_lru.hh:282
std::vector
STL vector class.
Definition: stl.hh:37
floorLog2
std::enable_if< std::is_integral< T >::value, int >::type floorLog2(T x)
Definition: intmath.hh:63
FALRU::insertBlock
void insertBlock(const PacketPtr pkt, CacheBlk *blk) override
Insert the new block into the cache and update replacement data.
Definition: fa_lru.cc:208
Stats::Vector
A vector of scalar stats.
Definition: statistics.hh:2575
FALRU::TagHash
std::unordered_map< TagHashKey, FALRUBlk *, PairHash > TagHash
Definition: fa_lru.hh:131
FALRU::CacheTracking
Mechanism that allows us to simultaneously collect miss statistics for multiple caches.
Definition: fa_lru.hh:279
packet.hh
FALRU::findBlock
CacheBlk * findBlock(Addr addr, bool is_secure) const override
Find the block in the cache, do not update the replacement data.
Definition: fa_lru.cc:169
Stats::Scalar
This is a simple scalar statistic, like a counter.
Definition: statistics.hh:2533
CachesMask
uint32_t CachesMask
Definition: fa_lru.hh:70
FALRU::CacheTracking::blkSize
const unsigned blkSize
The size of the cache block.
Definition: fa_lru.hh:360
FALRU::moveToTail
void moveToTail(FALRUBlk *blk)
Move a cache block to the LRU position.
Definition: fa_lru.cc:256
bitfield.hh
FALRU::CacheTracking::inAllCachesMask
const CachesMask inAllCachesMask
A mask for all cache being tracked.
Definition: fa_lru.hh:366
FALRU::CacheTracking::moveBlockToHead
void moveBlockToHead(FALRUBlk *blk)
Update boundaries as a block will be moved to the MRU.
Definition: fa_lru.cc:344
BaseTags
A common base class of Cache tagstore objects.
Definition: base.hh:70
FALRUBlk
A fully associative cache block.
Definition: fa_lru.hh:81
statistics.hh
FALRU::tagsInit
void tagsInit() override
Initialize blocks as FALRUBlk instances.
Definition: fa_lru.cc:83
BaseTags::Params
BaseTagsParams Params
Definition: base.hh:158
FALRUBlk::prev
FALRUBlk * prev
The previous block in LRU order.
Definition: fa_lru.hh:87
base.hh
FALRU::findVictim
CacheBlk * findVictim(Addr addr, const bool is_secure, const std::size_t size, std::vector< CacheBlk * > &evict_blks) override
Find replacement victim based on address.
Definition: fa_lru.cc:195
FALRU::~FALRU
~FALRU()
Definition: fa_lru.cc:77
FALRU::anyBlk
bool anyBlk(std::function< bool(CacheBlk &)> visitor) override
Find if any of the blocks satisfies a condition.
Definition: fa_lru.hh:263
BaseCache
A basic cache interface.
Definition: base.hh:89
std::pair
STL pair class.
Definition: stl.hh:58
FALRU::CacheTracking::check
void check(const FALRUBlk *head, const FALRUBlk *tail) const
Check that the tracking mechanism is in consistent state.
Definition: fa_lru.cc:289
FALRU::CacheTracking::moveBlockToTail
void moveBlockToTail(FALRUBlk *blk)
Update boundaries as a block will be moved to the LRU.
Definition: fa_lru.cc:370
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
FALRU::tagHash
TagHash tagHash
The address hash table.
Definition: fa_lru.hh:134
FALRU::CacheTracking::boundaries
std::vector< FALRUBlk * > boundaries
Array of pointers to blocks at the cache boundaries.
Definition: fa_lru.hh:368
FALRU::CacheTracking::accesses
Stats::Scalar accesses
Total number of accesses.
Definition: fa_lru.hh:383
FALRU::invalidate
void invalidate(CacheBlk *blk) override
Invalidate a cache block.
Definition: fa_lru.cc:117
FALRU::forEachBlk
void forEachBlk(std::function< void(CacheBlk &)> visitor) override
Visit each block in the tags and apply a visitor.
Definition: fa_lru.hh:257
CacheBlk::tag
Addr tag
Data block tag value.
Definition: cache_blk.hh:91
FALRU::PairHash
Hash table type mapping addresses to cache block pointers.
Definition: fa_lru.hh:122
SimObject::name
virtual const std::string name() const
Definition: sim_object.hh:133
FALRU::CacheTracking::init
void init(FALRUBlk *head, FALRUBlk *tail)
Initialiaze cache blocks and the tracking mechanism.
Definition: fa_lru.cc:317
FALRU::Params
FALRUParams Params
Definition: fa_lru.hh:151
cache_blk.hh
FALRU::moveToHead
void moveToHead(FALRUBlk *blk)
Move a cache block to the MRU position.
Definition: fa_lru.cc:229
CacheBlk
A Basic Cache block.
Definition: cache_blk.hh:84
types.hh
FALRU::regStats
void regStats() override
Register the stats for this object.
Definition: fa_lru.cc:110
FALRU::blks
FALRUBlk * blks
The cache blocks.
Definition: fa_lru.hh:114
Packet
A Packet is used to encapsulate a transfer between two objects in the memory system (e....
Definition: packet.hh:257
addr
ip6_addr_t addr
Definition: inet.hh:423
logging.hh
Cycles
Cycles is a wrapper class for representing cycle counts, i.e.
Definition: types.hh:83
FALRU::PairHash::operator()
std::size_t operator()(const std::pair< T1, T2 > &p) const
Definition: fa_lru.hh:125
FALRU::extractTag
Addr extractTag(Addr addr) const override
Generate the tag from the addres.
Definition: fa_lru.hh:241
MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:323
intmath.hh
FALRU
A fully associative LRU cache.
Definition: fa_lru.hh:106
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:219
FALRU::FALRU
FALRU(const Params *p)
Construct and initialize this cache tagstore.
Definition: fa_lru.cc:63
BaseTags::size
const unsigned size
The size of the cache.
Definition: base.hh:78
BaseTags::blkAlign
Addr blkAlign(Addr addr) const
Align an address to the block size.
Definition: base.hh:212
FALRU::findBlockBySetAndWay
ReplaceableEntry * findBlockBySetAndWay(int set, int way) const override
Find a block given set and way.
Definition: fa_lru.cc:188
ArmISA::mask
Bitfield< 28, 24 > mask
Definition: miscregs_types.hh:711
FALRU::CacheTracking::hits
Stats::Vector hits
Hits in each cache.
Definition: fa_lru.hh:379
FALRU::regenerateBlkAddr
Addr regenerateBlkAddr(const CacheBlk *blk) const override
Regenerate the block address from the tag.
Definition: fa_lru.hh:252

Generated on Wed Sep 30 2020 14:02:12 for gem5 by doxygen 1.8.17