cache/tags/fa_lru.hh

/*
 * 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 and set the parent cache back pointer.
     *
     * @param _cache Pointer to parent cache.
     */
    void tagsInit(BaseCache *_cache) 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__