src/mem/cache/tags/base_set_assoc.hh - amd/gem5 - Git at Google

 /*
  * Copyright (c) 2012-2014,2017 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,2014 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
  */

 /**
  * @file
  * Declaration of a base set associative tag store.
  */

 #ifndef __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__
 #define __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__

 #include <functional>
 #include <string>
 #include <vector>

 #include "base/logging.hh"
 #include "base/types.hh"
 #include "debug/CacheRepl.hh"
 #include "mem/cache/base.hh"
 #include "mem/cache/blk.hh"
 #include "mem/cache/replacement_policies/base.hh"
 #include "mem/cache/tags/base.hh"
 #include "mem/cache/tags/cacheset.hh"
 #include "mem/packet.hh"
 #include "params/BaseSetAssoc.hh"

 /**
  * A BaseSetAssoc cache tag store.
  * @sa  \ref gem5MemorySystem "gem5 Memory System"
  *
  * The BaseSetAssoc placement policy divides the cache into s sets of w
  * cache lines (ways). A cache line is mapped onto a set, and can be placed
  * into any of the ways of this set.
  */
 class BaseSetAssoc : public BaseTags
 {
   public:
     /** Typedef the block type used in this tag store. */
     typedef CacheBlk BlkType;
     /** Typedef the set type used in this tag store. */
     typedef CacheSet<CacheBlk> SetType;

   protected:
     /** The associativity of the cache. */
     const unsigned assoc;
     /** The allocatable associativity of the cache (alloc mask). */
     unsigned allocAssoc;

     /** The cache blocks. */
     std::vector<BlkType> blks;

     /** The number of sets in the cache. */
     const unsigned numSets;

     /** Whether tags and data are accessed sequentially. */
     const bool sequentialAccess;

     /** The cache sets. */
     std::vector<SetType> sets;

     /** The amount to shift the address to get the set. */
     int setShift;
     /** The amount to shift the address to get the tag. */
     int tagShift;
     /** Mask out all bits that aren't part of the set index. */
     unsigned setMask;

     /** Replacement policy */
     BaseReplacementPolicy *replacementPolicy;

   public:
     /** Convenience typedef. */
      typedef BaseSetAssocParams Params;

     /**
      * Construct and initialize this tag store.
      */
     BaseSetAssoc(const Params *p);

     /**
      * Destructor
      */
     virtual ~BaseSetAssoc() {};

     /**
      * This function updates the tags when a block is invalidated. It also
      * updates the replacement data.
      *
      * @param blk The block to invalidate.
      */
     void invalidate(CacheBlk *blk) override;

     /**
      * Access block and update replacement data. May not succeed, in which case
      * nullptr is returned. This has all the implications of a cache
      * access and should only be used as such. Returns the access latency as a
      * side effect.
      * @param addr The address to find.
      * @param is_secure True if the target memory space is secure.
      * @param lat The access latency.
      * @return Pointer to the cache block if found.
      */
     CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override
     {
         BlkType *blk = findBlock(addr, is_secure);

         // Access all tags in parallel, hence one in each way.  The data side
         // either accesses all blocks in parallel, or one block sequentially on
         // a hit.  Sequential access with a miss doesn't access data.
         tagAccesses += allocAssoc;
         if (sequentialAccess) {
             if (blk != nullptr) {
                 dataAccesses += 1;
             }
         } else {
             dataAccesses += allocAssoc;
         }

         if (blk != nullptr) {
             // If a cache hit
             lat = accessLatency;
             // Check if the block to be accessed is available. If not,
             // apply the accessLatency on top of block->whenReady.
             if (blk->whenReady > curTick() &&
                 cache->ticksToCycles(blk->whenReady - curTick()) >
                 accessLatency) {
                 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
                 accessLatency;
             }

             // Update number of references to accessed block
             blk->refCount++;

             // Update replacement data of accessed block
             replacementPolicy->touch(blk->replacementData);
         } else {
             // If a cache miss
             lat = lookupLatency;
         }

         return blk;
     }

     /**
      * Finds the given address in the cache, do not update replacement data.
      * i.e. This is a no-side-effect find of a block.
      * @param addr The address to find.
      * @param is_secure True if the target memory space is secure.
      * @param asid The address space ID.
      * @return Pointer to the cache block if found.
      */
     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 evict_blks Cache blocks to be evicted.
      * @return Cache block to be replaced.
      */
     CacheBlk* findVictim(Addr addr, std::vector<CacheBlk*>& evict_blks) const
                                                                      override
     {
         // Get possible locations for the victim block
         std::vector<CacheBlk*> locations = getPossibleLocations(addr);

         // Choose replacement victim from replacement candidates
         CacheBlk* victim = static_cast<CacheBlk*>(replacementPolicy->getVictim(
                                std::vector<ReplaceableEntry*>(
                                    locations.begin(), locations.end())));

         // There is only one eviction for this replacement
         evict_blks.push_back(victim);

         DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
             victim->set, victim->way);

         return victim;
     }

     /**
      * Find all possible block locations for insertion and replacement of
      * an address. Should be called immediately before ReplacementPolicy's
      * findVictim() not to break cache resizing.
      * Returns blocks in all ways belonging to the set of the address.
      *
      * @param addr The addr to a find possible locations for.
      * @return The possible locations.
      */
     const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const
     {
         return sets[extractSet(addr)].blks;
     }

     /**
      * Insert the new block into the cache and update replacement data.
      *
      * @param pkt Packet holding the address to update
      * @param blk The block to update.
      */
     void insertBlock(PacketPtr pkt, CacheBlk *blk) override
     {
         // Insert block
         BaseTags::insertBlock(pkt, blk);

         // Increment tag counter
         tagsInUse++;

         // Update replacement policy
         replacementPolicy->reset(blk->replacementData);
     }

     /**
      * Limit the allocation for the cache ways.
      * @param ways The maximum number of ways available for replacement.
      */
     virtual void setWayAllocationMax(int ways) override
     {
         fatal_if(ways < 1, "Allocation limit must be greater than zero");
         allocAssoc = ways;
     }

     /**
      * Get the way allocation mask limit.
      * @return The maximum number of ways available for replacement.
      */
     virtual int getWayAllocationMax() const override
     {
         return allocAssoc;
     }

     /**
      * Generate the tag from the given address.
      * @param addr The address to get the tag from.
      * @return The tag of the address.
      */
     Addr extractTag(Addr addr) const override
     {
         return (addr >> tagShift);
     }

     /**
      * Regenerate the block address from the tag and set.
      *
      * @param block The block.
      * @return the block address.
      */
     Addr regenerateBlkAddr(const CacheBlk* blk) const override
     {
         return ((blk->tag << tagShift) | ((Addr)blk->set << setShift));
     }

     void forEachBlk(std::function<void(CacheBlk &)> visitor) override {
         for (CacheBlk& blk : blks) {
             visitor(blk);
         }
     }

     bool anyBlk(std::function<bool(CacheBlk &)> visitor) override {
         for (CacheBlk& blk : blks) {
             if (visitor(blk)) {
                 return true;
             }
         }
         return false;
     }

   private:
     /**
      * Calculate the set index from the address.
      *
      * @param addr The address to get the set from.
      * @return The set index of the address.
      */
     int extractSet(Addr addr) const
     {
         return ((addr >> setShift) & setMask);
     }
 };

 #endif //__MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__
	/*
	* Copyright (c) 2012-2014,2017 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,2014 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
	*/

	/**
	* @file
	* Declaration of a base set associative tag store.
	*/

	#ifndef __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__
	#define __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__

	#include <functional>
	#include <string>
	#include <vector>

	#include "base/logging.hh"
	#include "base/types.hh"
	#include "debug/CacheRepl.hh"
	#include "mem/cache/base.hh"
	#include "mem/cache/blk.hh"
	#include "mem/cache/replacement_policies/base.hh"
	#include "mem/cache/tags/base.hh"
	#include "mem/cache/tags/cacheset.hh"
	#include "mem/packet.hh"
	#include "params/BaseSetAssoc.hh"

	/**
	* A BaseSetAssoc cache tag store.
	* @sa \ref gem5MemorySystem "gem5 Memory System"
	*
	* The BaseSetAssoc placement policy divides the cache into s sets of w
	* cache lines (ways). A cache line is mapped onto a set, and can be placed
	* into any of the ways of this set.
	*/
	class BaseSetAssoc : public BaseTags
	{
	public:
	/** Typedef the block type used in this tag store. */
	typedef CacheBlk BlkType;
	/** Typedef the set type used in this tag store. */
	typedef CacheSet<CacheBlk> SetType;

	protected:
	/** The associativity of the cache. */
	const unsigned assoc;
	/** The allocatable associativity of the cache (alloc mask). */
	unsigned allocAssoc;

	/** The cache blocks. */
	std::vector<BlkType> blks;

	/** The number of sets in the cache. */
	const unsigned numSets;

	/** Whether tags and data are accessed sequentially. */
	const bool sequentialAccess;

	/** The cache sets. */
	std::vector<SetType> sets;

	/** The amount to shift the address to get the set. */
	int setShift;
	/** The amount to shift the address to get the tag. */
	int tagShift;
	/** Mask out all bits that aren't part of the set index. */
	unsigned setMask;

	/** Replacement policy */
	BaseReplacementPolicy *replacementPolicy;

	public:
	/** Convenience typedef. */
	typedef BaseSetAssocParams Params;

	/**
	* Construct and initialize this tag store.
	*/
	BaseSetAssoc(const Params *p);

	/**
	* Destructor
	*/
	virtual ~BaseSetAssoc() {};

	/**
	* This function updates the tags when a block is invalidated. It also
	* updates the replacement data.
	*
	* @param blk The block to invalidate.
	*/
	void invalidate(CacheBlk *blk) override;

	/**
	* Access block and update replacement data. May not succeed, in which case
	* nullptr is returned. This has all the implications of a cache
	* access and should only be used as such. Returns the access latency as a
	* side effect.
	* @param addr The address to find.
	* @param is_secure True if the target memory space is secure.
	* @param lat The access latency.
	* @return Pointer to the cache block if found.
	*/
	CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override
	{
	BlkType *blk = findBlock(addr, is_secure);

	// Access all tags in parallel, hence one in each way. The data side
	// either accesses all blocks in parallel, or one block sequentially on
	// a hit. Sequential access with a miss doesn't access data.
	tagAccesses += allocAssoc;
	if (sequentialAccess) {
	if (blk != nullptr) {
	dataAccesses += 1;
	}
	} else {
	dataAccesses += allocAssoc;
	}

	if (blk != nullptr) {
	// If a cache hit
	lat = accessLatency;
	// Check if the block to be accessed is available. If not,
	// apply the accessLatency on top of block->whenReady.
	if (blk->whenReady > curTick() &&
	cache->ticksToCycles(blk->whenReady - curTick()) >
	accessLatency) {
	lat = cache->ticksToCycles(blk->whenReady - curTick()) +
	accessLatency;
	}

	// Update number of references to accessed block
	blk->refCount++;

	// Update replacement data of accessed block
	replacementPolicy->touch(blk->replacementData);
	} else {
	// If a cache miss
	lat = lookupLatency;
	}

	return blk;
	}

	/**
	* Finds the given address in the cache, do not update replacement data.
	* i.e. This is a no-side-effect find of a block.
	* @param addr The address to find.
	* @param is_secure True if the target memory space is secure.
	* @param asid The address space ID.
	* @return Pointer to the cache block if found.
	*/
	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 evict_blks Cache blocks to be evicted.
	* @return Cache block to be replaced.
	*/
	CacheBlk* findVictim(Addr addr, std::vector<CacheBlk*>& evict_blks) const
	override
	{
	// Get possible locations for the victim block
	std::vector<CacheBlk*> locations = getPossibleLocations(addr);

	// Choose replacement victim from replacement candidates
	CacheBlk* victim = static_cast<CacheBlk*>(replacementPolicy->getVictim(
	std::vector<ReplaceableEntry*>(
	locations.begin(), locations.end())));

	// There is only one eviction for this replacement
	evict_blks.push_back(victim);

	DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
	victim->set, victim->way);

	return victim;
	}

	/**
	* Find all possible block locations for insertion and replacement of
	* an address. Should be called immediately before ReplacementPolicy's
	* findVictim() not to break cache resizing.
	* Returns blocks in all ways belonging to the set of the address.
	*
	* @param addr The addr to a find possible locations for.
	* @return The possible locations.
	*/
	const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const
	{
	return sets[extractSet(addr)].blks;
	}

	/**
	* Insert the new block into the cache and update replacement data.
	*
	* @param pkt Packet holding the address to update
	* @param blk The block to update.
	*/
	void insertBlock(PacketPtr pkt, CacheBlk *blk) override
	{
	// Insert block
	BaseTags::insertBlock(pkt, blk);

	// Increment tag counter
	tagsInUse++;

	// Update replacement policy
	replacementPolicy->reset(blk->replacementData);
	}

	/**
	* Limit the allocation for the cache ways.
	* @param ways The maximum number of ways available for replacement.
	*/
	virtual void setWayAllocationMax(int ways) override
	{
	fatal_if(ways < 1, "Allocation limit must be greater than zero");
	allocAssoc = ways;
	}

	/**
	* Get the way allocation mask limit.
	* @return The maximum number of ways available for replacement.
	*/
	virtual int getWayAllocationMax() const override
	{
	return allocAssoc;
	}

	/**
	* Generate the tag from the given address.
	* @param addr The address to get the tag from.
	* @return The tag of the address.
	*/
	Addr extractTag(Addr addr) const override
	{
	return (addr >> tagShift);
	}

	/**
	* Regenerate the block address from the tag and set.
	*
	* @param block The block.
	* @return the block address.
	*/
	Addr regenerateBlkAddr(const CacheBlk* blk) const override
	{
	return ((blk->tag << tagShift) \| ((Addr)blk->set << setShift));
	}

	void forEachBlk(std::function<void(CacheBlk &)> visitor) override {
	for (CacheBlk& blk : blks) {
	visitor(blk);
	}
	}

	bool anyBlk(std::function<bool(CacheBlk &)> visitor) override {
	for (CacheBlk& blk : blks) {
	if (visitor(blk)) {
	return true;
	}
	}
	return false;
	}

	private:
	/**
	* Calculate the set index from the address.
	*
	* @param addr The address to get the set from.
	* @return The set index of the address.
	*/
	int extractSet(Addr addr) const
	{
	return ((addr >> setShift) & setMask);
	}
	};

	#endif //__MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__