gem5  v21.1.0.2
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 namespace gem5
66 {
67 
68 // Uncomment to enable sanity checks for the FALRU cache and the
69 // TrackedCaches class
70 //#define FALRU_DEBUG
71 
72 class BaseCache;
74 
75 // A bitmask of the caches we are keeping track of. Currently the
76 // lowest bit is the smallest cache we are tracking, as it is
77 // specified by the corresponding parameter. The rest of the bits are
78 // for exponentially growing cache sizes.
79 typedef uint32_t CachesMask;
80 
84 class FALRUBlk : public CacheBlk
85 {
86  public:
87  FALRUBlk() : CacheBlk(), prev(nullptr), next(nullptr), inCachesMask(0) {}
88 
93 
96 
102  std::string print() const override;
103 };
104 
109 class FALRU : public BaseTags
110 {
111  public:
113  typedef FALRUBlk BlkType;
114 
115  protected:
118 
123 
125  struct PairHash
126  {
127  template <class T1, class T2>
128  std::size_t operator()(const std::pair<T1, T2> &p) const
129  {
130  return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second);
131  }
132  };
134  typedef std::unordered_map<TagHashKey, FALRUBlk *, PairHash> TagHash;
135 
138 
144  void moveToHead(FALRUBlk *blk);
145 
151  void moveToTail(FALRUBlk *blk);
152 
153  public:
154  typedef FALRUParams Params;
155 
159  FALRU(const Params &p);
160  ~FALRU();
161 
165  void tagsInit() override;
166 
171  void invalidate(CacheBlk *blk) override;
172 
184  CacheBlk* accessBlock(const PacketPtr pkt, Cycles &lat,
185  CachesMask *in_cache_mask);
186 
190  CacheBlk* accessBlock(const PacketPtr pkt, Cycles &lat) override;
191 
199  CacheBlk* findBlock(Addr addr, bool is_secure) const override;
200 
208  ReplaceableEntry* findBlockBySetAndWay(int set, int way) const override;
209 
220  CacheBlk* findVictim(Addr addr, const bool is_secure,
221  const std::size_t size,
222  std::vector<CacheBlk*>& evict_blks) override;
223 
230  void insertBlock(const PacketPtr pkt, CacheBlk *blk) override;
231 
232  void moveBlock(CacheBlk *src_blk, CacheBlk *dest_blk) override;
233 
240  Addr extractTag(Addr addr) const override
241  {
242  return blkAlign(addr);
243  }
244 
251  Addr regenerateBlkAddr(const CacheBlk* blk) const override
252  {
253  return blk->getTag();
254  }
255 
256  void forEachBlk(std::function<void(CacheBlk &)> visitor) override {
257  for (int i = 0; i < numBlocks; i++) {
258  visitor(blks[i]);
259  }
260  }
261 
262  bool anyBlk(std::function<bool(CacheBlk &)> visitor) override {
263  for (int i = 0; i < numBlocks; i++) {
264  if (visitor(blks[i])) {
265  return true;
266  }
267  }
268  return false;
269  }
270 
271  private:
279  {
280  public:
281  CacheTracking(unsigned min_size, unsigned max_size,
282  unsigned block_size, statistics::Group *parent);
283 
292  void init(FALRUBlk *head, FALRUBlk *tail);
293 
303  void moveBlockToHead(FALRUBlk *blk);
304 
314  void moveBlockToTail(FALRUBlk *blk);
315 
326  void recordAccess(FALRUBlk *blk);
327 
338  void check(const FALRUBlk *head, const FALRUBlk *tail) const;
339 
340  private:
342  const unsigned blkSize;
344  const unsigned minTrackedSize;
346  const int numTrackedCaches;
351 
352  protected:
366 
370  };
372 };
373 
374 } // namespace gem5
375 
376 #endif // __MEM_CACHE_TAGS_FA_LRU_HH__
gem5::statistics::Scalar
This is a simple scalar statistic, like a counter.
Definition: statistics.hh:1927
gem5::FALRU::CacheTracking::hits
statistics::Vector hits
Hits in each cache.
Definition: fa_lru.hh:361
gem5::FALRU::CacheTracking::inAllCachesMask
const CachesMask inAllCachesMask
A mask for all cache being tracked.
Definition: fa_lru.hh:348
gem5::FALRUBlk::FALRUBlk
FALRUBlk()
Definition: fa_lru.hh:87
gem5::FALRU::PairHash::operator()
std::size_t operator()(const std::pair< T1, T2 > &p) const
Definition: fa_lru.hh:128
gem5::FALRU::CacheTracking::blkSize
const unsigned blkSize
The size of the cache block.
Definition: fa_lru.hh:342
gem5::FALRU::findBlockBySetAndWay
ReplaceableEntry * findBlockBySetAndWay(int set, int way) const override
Find a block given set and way.
Definition: fa_lru.cc:186
gem5::FALRU::BlkType
FALRUBlk BlkType
Typedef the block type used in this class.
Definition: fa_lru.hh:113
gem5::FALRU::CacheTracking::accesses
statistics::Scalar accesses
Total number of accesses.
Definition: fa_lru.hh:365
gem5::FALRU::CacheTracking::numTrackedCaches
const int numTrackedCaches
The number of different size caches being tracked.
Definition: fa_lru.hh:346
gem5::FALRU::moveToHead
void moveToHead(FALRUBlk *blk)
Move a cache block to the MRU position.
Definition: fa_lru.cc:233
gem5::FALRUBlk::print
std::string print() const override
Pretty-print inCachesMask and other CacheBlk information.
Definition: fa_lru.cc:62
gem5::FALRU::FALRU
FALRU(const Params &p)
Construct and initialize this cache tagstore.
Definition: fa_lru.cc:67
gem5::statistics::Vector
A vector of scalar stats.
Definition: statistics.hh:2003
std::vector
STL vector class.
Definition: stl.hh:37
gem5::TaggedEntry::getTag
virtual Addr getTag() const
Get tag associated to this block.
Definition: tagged_entry.hh:71
gem5::FALRU::invalidate
void invalidate(CacheBlk *blk) override
Invalidate a cache block.
Definition: fa_lru.cc:114
gem5::BaseTags::numBlocks
const unsigned numBlocks
the number of blocks in the cache
Definition: base.hh:100
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::CachesMask
uint32_t CachesMask
Definition: fa_lru.hh:73
gem5::BaseTags::blkAlign
Addr blkAlign(Addr addr) const
Align an address to the block size.
Definition: base.hh:215
gem5::CacheBlk
A Basic Cache block.
Definition: cache_blk.hh:70
packet.hh
gem5::FALRU::CacheTracking::minTrackedSize
const unsigned minTrackedSize
The smallest cache we are tracking.
Definition: fa_lru.hh:344
gem5::Cycles
Cycles is a wrapper class for representing cycle counts, i.e.
Definition: types.hh:78
gem5::BaseTags::Params
BaseTagsParams Params
Definition: base.hh:161
gem5::FALRU::CacheTracking::misses
statistics::Vector misses
Misses in each cache.
Definition: fa_lru.hh:363
gem5::BaseTags::size
const unsigned size
The size of the cache.
Definition: base.hh:81
gem5::FALRU::blks
FALRUBlk * blks
The cache blocks.
Definition: fa_lru.hh:117
gem5::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:167
bitfield.hh
gem5::FALRU::PairHash
Hash table type mapping addresses to cache block pointers.
Definition: fa_lru.hh:125
gem5::FALRU::CacheTracking::recordAccess
void recordAccess(FALRUBlk *blk)
Notify of a block access.
Definition: fa_lru.cc:441
gem5::Packet
A Packet is used to encapsulate a transfer between two objects in the memory system (e....
Definition: packet.hh:283
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
statistics.hh
gem5::FALRU::CacheTracking::init
void init(FALRUBlk *head, FALRUBlk *tail)
Initialiaze cache blocks and the tracking mechanism.
Definition: fa_lru.cc:363
gem5::FALRU::CacheTracking::moveBlockToHead
void moveBlockToHead(FALRUBlk *blk)
Update boundaries as a block will be moved to the MRU.
Definition: fa_lru.cc:390
gem5::FALRU::extractTag
Addr extractTag(Addr addr) const override
Generate the tag from the addres.
Definition: fa_lru.hh:240
gem5::FALRU::TagHashKey
std::pair< Addr, bool > TagHashKey
Definition: fa_lru.hh:133
base.hh
gem5::FALRU::head
FALRUBlk * head
The MRU block.
Definition: fa_lru.hh:120
gem5::FALRU::TagHash
std::unordered_map< TagHashKey, FALRUBlk *, PairHash > TagHash
Definition: fa_lru.hh:134
gem5::FALRUBlk::inCachesMask
CachesMask inCachesMask
A bit mask of the caches that fit this block.
Definition: fa_lru.hh:95
gem5::FALRU::cacheTracking
CacheTracking cacheTracking
Definition: fa_lru.hh:371
std::pair
STL pair class.
Definition: stl.hh:58
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::FALRU::regenerateBlkAddr
Addr regenerateBlkAddr(const CacheBlk *blk) const override
Regenerate the block address from the tag.
Definition: fa_lru.hh:251
gem5::FALRU::CacheTracking::boundaries
std::vector< FALRUBlk * > boundaries
Array of pointers to blocks at the cache boundaries.
Definition: fa_lru.hh:350
gem5::FALRUBlk::next
FALRUBlk * next
The next block in LRU order.
Definition: fa_lru.hh:92
gem5::FALRU::accessBlock
CacheBlk * accessBlock(const PacketPtr pkt, Cycles &lat, CachesMask *in_cache_mask)
Access block and update replacement data.
Definition: fa_lru.cc:140
gem5::FALRU::CacheTracking
Mechanism that allows us to simultaneously collect miss statistics for multiple caches.
Definition: fa_lru.hh:278
gem5::FALRU::anyBlk
bool anyBlk(std::function< bool(CacheBlk &)> visitor) override
Find if any of the blocks satisfies a condition.
Definition: fa_lru.hh:262
gem5::FALRU::tagHash
TagHash tagHash
The address hash table.
Definition: fa_lru.hh:137
gem5::FALRU::moveBlock
void moveBlock(CacheBlk *src_blk, CacheBlk *dest_blk) override
Move a block's metadata to another location decided by the replacement policy.
Definition: fa_lru.cc:227
cache_blk.hh
gem5::FALRU::tail
FALRUBlk * tail
The LRU block.
Definition: fa_lru.hh:122
gem5::FALRUBlk::prev
FALRUBlk * prev
The previous block in LRU order.
Definition: fa_lru.hh:90
types.hh
gem5::ReplaceableEntry
A replaceable entry is a basic entry in a 2d table-like structure that needs to have replacement func...
Definition: replaceable_entry.hh:63
gem5::FALRU::CacheTracking::moveBlockToTail
void moveBlockToTail(FALRUBlk *blk)
Update boundaries as a block will be moved to the LRU.
Definition: fa_lru.cc:416
gem5::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:206
gem5::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:193
gem5::FALRU::forEachBlk
void forEachBlk(std::function< void(CacheBlk &)> visitor) override
Visit each block in the tags and apply a visitor.
Definition: fa_lru.hh:256
logging.hh
gem5::statistics::Group
Statistics container.
Definition: group.hh:93
gem5::FALRU
A fully associative LRU cache.
Definition: fa_lru.hh:109
gem5::FALRU::moveToTail
void moveToTail(FALRUBlk *blk)
Move a cache block to the LRU position.
Definition: fa_lru.cc:260
gem5::FALRU::CacheTracking::CacheTracking
CacheTracking(unsigned min_size, unsigned max_size, unsigned block_size, statistics::Group *parent)
Definition: fa_lru.cc:298
gem5::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:335
gem5::FALRU::~FALRU
~FALRU()
Definition: fa_lru.cc:81
intmath.hh
gem5::FALRU::tagsInit
void tagsInit() override
Initialize blocks as FALRUBlk instances.
Definition: fa_lru.cc:87
gem5::BaseTags
A common base class of Cache tagstore objects.
Definition: base.hh:73
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::FALRUBlk
A fully associative cache block.
Definition: fa_lru.hh:84
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition: types.hh:84
gem5::FALRU::Params
FALRUParams Params
Definition: fa_lru.hh:154

Generated on Tue Sep 21 2021 12:25:30 for gem5 by doxygen 1.8.17