| /* |
| * Copyright (c) 2012-2013,2016,2018 ARM Limited |
| * All rights reserved. |
| * |
| * The license below extends only to copyright in the software and shall |
| * not be construed as granting a license to any other intellectual |
| * property including but not limited to intellectual property relating |
| * to a hardware implementation of the functionality of the software |
| * licensed hereunder. You may use the software subject to the license |
| * terms below provided that you ensure that this notice is replicated |
| * unmodified and in its entirety in all distributions of the software, |
| * modified or unmodified, in source code or in binary form. |
| * |
| * Copyright (c) 2003-2005 The Regents of The University of Michigan |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer; |
| * redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution; |
| * neither the name of the copyright holders nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Authors: Erik Hallnor |
| * Nikos Nikoleris |
| */ |
| |
| /** |
| * @file |
| * Declaration of a fully associative LRU tag store. |
| */ |
| |
| #ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ |
| #define __MEM_CACHE_TAGS_FA_LRU_HH__ |
| |
| #include <cstdint> |
| #include <functional> |
| #include <string> |
| #include <unordered_map> |
| #include <vector> |
| |
| #include "base/bitfield.hh" |
| #include "base/intmath.hh" |
| #include "base/logging.hh" |
| #include "base/statistics.hh" |
| #include "base/types.hh" |
| #include "mem/cache/cache_blk.hh" |
| #include "mem/cache/tags/base.hh" |
| #include "params/FALRU.hh" |
| |
| // Uncomment to enable sanity checks for the FALRU cache and the |
| // TrackedCaches class |
| //#define FALRU_DEBUG |
| |
| class BaseCache; |
| class ReplaceableEntry; |
| |
| // A bitmask of the caches we are keeping track of. Currently the |
| // lowest bit is the smallest cache we are tracking, as it is |
| // specified by the corresponding parameter. The rest of the bits are |
| // for exponentially growing cache sizes. |
| typedef uint32_t CachesMask; |
| |
| /** |
| * A fully associative cache block. |
| */ |
| class FALRUBlk : public CacheBlk |
| { |
| public: |
| FALRUBlk() : CacheBlk(), prev(nullptr), next(nullptr), inCachesMask(0) {} |
| |
| /** The previous block in LRU order. */ |
| FALRUBlk *prev; |
| /** The next block in LRU order. */ |
| FALRUBlk *next; |
| |
| /** A bit mask of the caches that fit this block. */ |
| CachesMask inCachesMask; |
| |
| /** |
| * Pretty-print inCachesMask and other CacheBlk information. |
| * |
| * @return string with basic state information |
| */ |
| std::string print() const override; |
| }; |
| |
| /** |
| * A fully associative LRU cache. Keeps statistics for accesses to a number of |
| * cache sizes at once. |
| */ |
| class FALRU : public BaseTags |
| { |
| public: |
| /** Typedef the block type used in this class. */ |
| typedef FALRUBlk BlkType; |
| |
| protected: |
| /** The cache blocks. */ |
| FALRUBlk *blks; |
| |
| /** The MRU block. */ |
| FALRUBlk *head; |
| /** The LRU block. */ |
| FALRUBlk *tail; |
| |
| /** Hash table type mapping addresses to cache block pointers. */ |
| struct PairHash |
| { |
| template <class T1, class T2> |
| std::size_t operator()(const std::pair<T1, T2> &p) const |
| { |
| return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second); |
| } |
| }; |
| typedef std::pair<Addr, bool> TagHashKey; |
| typedef std::unordered_map<TagHashKey, FALRUBlk *, PairHash> TagHash; |
| |
| /** The address hash table. */ |
| TagHash tagHash; |
| |
| /** |
| * Move a cache block to the MRU position. |
| * |
| * @param blk The block to promote. |
| */ |
| void moveToHead(FALRUBlk *blk); |
| |
| /** |
| * Move a cache block to the LRU position. |
| * |
| * @param blk The block to demote. |
| */ |
| void moveToTail(FALRUBlk *blk); |
| |
| public: |
| typedef FALRUParams Params; |
| |
| /** |
| * Construct and initialize this cache tagstore. |
| */ |
| FALRU(const Params *p); |
| ~FALRU(); |
| |
| /** |
| * Initialize blocks as FALRUBlk instances. |
| */ |
| void tagsInit() override; |
| |
| /** |
| * Register the stats for this object. |
| */ |
| void regStats() override; |
| |
| /** |
| * Invalidate a cache block. |
| * @param blk The block to invalidate. |
| */ |
| void invalidate(CacheBlk *blk) override; |
| |
| /** |
| * Access block and update replacement data. May not succeed, in which |
| * case nullptr pointer is returned. This has all the implications of a |
| * cache access and should only be used as such. |
| * Returns tag lookup latency and the inCachesMask flags as a side effect. |
| * |
| * @param addr The address to look for. |
| * @param is_secure True if the target memory space is secure. |
| * @param lat The latency of the tag lookup. |
| * @param in_cache_mask Mask indicating the caches in which the blk fits. |
| * @return Pointer to the cache block. |
| */ |
| CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, |
| CachesMask *in_cache_mask); |
| |
| /** |
| * Just a wrapper of above function to conform with the base interface. |
| */ |
| CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override; |
| |
| /** |
| * Find the block in the cache, do not update the replacement data. |
| * @param addr The address to look for. |
| * @param is_secure True if the target memory space is secure. |
| * @param asid The address space ID. |
| * @return Pointer to the cache block. |
| */ |
| CacheBlk* findBlock(Addr addr, bool is_secure) const override; |
| |
| /** |
| * Find a block given set and way. |
| * |
| * @param set The set of the block. |
| * @param way The way of the block. |
| * @return The block. |
| */ |
| ReplaceableEntry* findBlockBySetAndWay(int set, int way) const override; |
| |
| /** |
| * Find replacement victim based on address. The list of evicted blocks |
| * only contains the victim. |
| * |
| * @param addr Address to find a victim for. |
| * @param is_secure True if the target memory space is secure. |
| * @param evict_blks Cache blocks to be evicted. |
| * @return Cache block to be replaced. |
| */ |
| CacheBlk* findVictim(Addr addr, const bool is_secure, |
| std::vector<CacheBlk*>& evict_blks) const override; |
| |
| /** |
| * Insert the new block into the cache and update replacement data. |
| * |
| * @param addr Address of the block. |
| * @param is_secure Whether the block is in secure space or not. |
| * @param src_master_ID The source requestor ID. |
| * @param task_ID The new task ID. |
| * @param blk The block to update. |
| */ |
| void insertBlock(const Addr addr, const bool is_secure, |
| const int src_master_ID, const uint32_t task_ID, |
| CacheBlk *blk) override; |
| |
| /** |
| * Generate the tag from the addres. For fully associative this is just the |
| * block address. |
| * @param addr The address to get the tag from. |
| * @return The tag. |
| */ |
| Addr extractTag(Addr addr) const override |
| { |
| return blkAlign(addr); |
| } |
| |
| /** |
| * Regenerate the block address from the tag. |
| * |
| * @param block The block. |
| * @return the block address. |
| */ |
| Addr regenerateBlkAddr(const CacheBlk* blk) const override |
| { |
| return blk->tag; |
| } |
| |
| void forEachBlk(std::function<void(CacheBlk &)> visitor) override { |
| for (int i = 0; i < numBlocks; i++) { |
| visitor(blks[i]); |
| } |
| } |
| |
| bool anyBlk(std::function<bool(CacheBlk &)> visitor) override { |
| for (int i = 0; i < numBlocks; i++) { |
| if (visitor(blks[i])) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| private: |
| /** |
| * Mechanism that allows us to simultaneously collect miss |
| * statistics for multiple caches. Currently, we keep track of |
| * caches from a set minimum size of interest up to the actual |
| * cache size. |
| */ |
| class CacheTracking |
| { |
| public: |
| CacheTracking(unsigned min_size, unsigned max_size, |
| unsigned block_size) |
| : blkSize(block_size), |
| minTrackedSize(min_size), |
| numTrackedCaches(max_size > min_size ? |
| floorLog2(max_size) - floorLog2(min_size) : 0), |
| inAllCachesMask(mask(numTrackedCaches)), |
| boundaries(numTrackedCaches) |
| { |
| fatal_if(numTrackedCaches > sizeof(CachesMask) * 8, |
| "Not enough bits (%s) in type CachesMask type to keep " |
| "track of %d caches\n", sizeof(CachesMask), |
| numTrackedCaches); |
| } |
| |
| /** |
| * Initialiaze cache blocks and the tracking mechanism |
| * |
| * All blocks in the cache need to be initialized once. |
| * |
| * @param blk the MRU block |
| * @param blk the LRU block |
| */ |
| void init(FALRUBlk *head, FALRUBlk *tail); |
| |
| /** |
| * Update boundaries as a block will be moved to the MRU. |
| * |
| * For all caches that didn't fit the block before moving it, |
| * we move their boundaries one block closer to the MRU. We |
| * also update InCacheMasks as neccessary. |
| * |
| * @param blk the block that will be moved to the head |
| */ |
| void moveBlockToHead(FALRUBlk *blk); |
| |
| /** |
| * Update boundaries as a block will be moved to the LRU. |
| * |
| * For all caches that fitted the block before moving it, we |
| * move their boundaries one block closer to the LRU. We |
| * also update InCacheMasks as neccessary. |
| * |
| * @param blk the block that will be moved to the head |
| */ |
| void moveBlockToTail(FALRUBlk *blk); |
| |
| /** |
| * Notify of a block access. |
| * |
| * This should be called every time a block is accessed and it |
| * updates statistics. If the input block is nullptr then we |
| * treat the access as a miss. The block's InCacheMask |
| * determines the caches in which the block fits. |
| * |
| * @param blk the block to record the access for |
| */ |
| void recordAccess(FALRUBlk *blk); |
| |
| /** |
| * Check that the tracking mechanism is in consistent state. |
| * |
| * Iterate from the head (MRU) to the tail (LRU) of the list |
| * of blocks and assert the inCachesMask and the boundaries |
| * are in consistent state. |
| * |
| * @param head the MRU block of the actual cache |
| * @param head the LRU block of the actual cache |
| */ |
| void check(const FALRUBlk *head, const FALRUBlk *tail) const; |
| |
| /** |
| * Register the stats for this object. |
| */ |
| void regStats(std::string name); |
| |
| private: |
| /** The size of the cache block */ |
| const unsigned blkSize; |
| /** The smallest cache we are tracking */ |
| const unsigned minTrackedSize; |
| /** The number of different size caches being tracked. */ |
| const int numTrackedCaches; |
| /** A mask for all cache being tracked. */ |
| const CachesMask inAllCachesMask; |
| /** Array of pointers to blocks at the cache boundaries. */ |
| std::vector<FALRUBlk*> boundaries; |
| |
| protected: |
| /** |
| * @defgroup FALRUStats Fully Associative LRU specific statistics |
| * The FA lru stack lets us track multiple cache sizes at once. These |
| * statistics track the hits and misses for different cache sizes. |
| * @{ |
| */ |
| |
| /** Hits in each cache */ |
| Stats::Vector hits; |
| /** Misses in each cache */ |
| Stats::Vector misses; |
| /** Total number of accesses */ |
| Stats::Scalar accesses; |
| |
| /** |
| * @} |
| */ |
| }; |
| CacheTracking cacheTracking; |
| }; |
| |
| #endif // __MEM_CACHE_TAGS_FA_LRU_HH__ |