fa_lru.hh revision 3862
12810Srdreslin@umich.edu/* 22810Srdreslin@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 32810Srdreslin@umich.edu * All rights reserved. 42810Srdreslin@umich.edu * 52810Srdreslin@umich.edu * Redistribution and use in source and binary forms, with or without 62810Srdreslin@umich.edu * modification, are permitted provided that the following conditions are 72810Srdreslin@umich.edu * met: redistributions of source code must retain the above copyright 82810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer; 92810Srdreslin@umich.edu * redistributions in binary form must reproduce the above copyright 102810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer in the 112810Srdreslin@umich.edu * documentation and/or other materials provided with the distribution; 122810Srdreslin@umich.edu * neither the name of the copyright holders nor the names of its 132810Srdreslin@umich.edu * contributors may be used to endorse or promote products derived from 142810Srdreslin@umich.edu * this software without specific prior written permission. 152810Srdreslin@umich.edu * 162810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272810Srdreslin@umich.edu * 282810Srdreslin@umich.edu * Authors: Erik Hallnor 292810Srdreslin@umich.edu */ 302810Srdreslin@umich.edu 312810Srdreslin@umich.edu/** 322810Srdreslin@umich.edu * @file 332810Srdreslin@umich.edu * Declaration of a fully associative LRU tag store. 342810Srdreslin@umich.edu */ 352810Srdreslin@umich.edu 362810Srdreslin@umich.edu#ifndef __FA_LRU_HH__ 372810Srdreslin@umich.edu#define __FA_LRU_HH__ 382810Srdreslin@umich.edu 392810Srdreslin@umich.edu#include <list> 402810Srdreslin@umich.edu 412810Srdreslin@umich.edu#include "mem/cache/cache_blk.hh" 422810Srdreslin@umich.edu#include "mem/packet.hh" 432810Srdreslin@umich.edu#include "base/hashmap.hh" 442810Srdreslin@umich.edu#include "mem/cache/tags/base_tags.hh" 452810Srdreslin@umich.edu 462810Srdreslin@umich.edu/** 472810Srdreslin@umich.edu * A fully associative cache block. 482810Srdreslin@umich.edu */ 492810Srdreslin@umich.educlass FALRUBlk : public CacheBlk 502810Srdreslin@umich.edu{ 512810Srdreslin@umich.edupublic: 522810Srdreslin@umich.edu /** The previous block in LRU order. */ 532810Srdreslin@umich.edu FALRUBlk *prev; 542810Srdreslin@umich.edu /** The next block in LRU order. */ 552810Srdreslin@umich.edu FALRUBlk *next; 562810Srdreslin@umich.edu /** Has this block been touched? */ 572810Srdreslin@umich.edu bool isTouched; 582810Srdreslin@umich.edu 592810Srdreslin@umich.edu /** 602810Srdreslin@umich.edu * A bit mask of the sizes of cache that this block is resident in. 612810Srdreslin@umich.edu * Each bit represents a power of 2 in MB size cache. 622810Srdreslin@umich.edu * If bit 0 is set, this block is in a 1MB cache 632810Srdreslin@umich.edu * If bit 2 is set, this block is in a 4MB cache, etc. 642810Srdreslin@umich.edu * There is one bit for each cache smaller than the full size (default 652810Srdreslin@umich.edu * 16MB). 662810Srdreslin@umich.edu */ 672810Srdreslin@umich.edu int inCache; 682810Srdreslin@umich.edu}; 692810Srdreslin@umich.edu 702810Srdreslin@umich.edu/** 712810Srdreslin@umich.edu * A fully associative LRU cache. Keeps statistics for accesses to a number of 722810Srdreslin@umich.edu * cache sizes at once. 732810Srdreslin@umich.edu */ 742810Srdreslin@umich.educlass FALRU : public BaseTags 752810Srdreslin@umich.edu{ 762810Srdreslin@umich.edu public: 772810Srdreslin@umich.edu /** Typedef the block type used in this class. */ 782810Srdreslin@umich.edu typedef FALRUBlk BlkType; 792810Srdreslin@umich.edu /** Typedef a list of pointers to the local block type. */ 802810Srdreslin@umich.edu typedef std::list<FALRUBlk*> BlkList; 812810Srdreslin@umich.edu protected: 822810Srdreslin@umich.edu /** The block size of the cache. */ 832810Srdreslin@umich.edu const int blkSize; 842810Srdreslin@umich.edu /** The size of the cache. */ 852810Srdreslin@umich.edu const int size; 862810Srdreslin@umich.edu /** The number of blocks in the cache. */ 872810Srdreslin@umich.edu const int numBlks; // calculated internally 882810Srdreslin@umich.edu /** The hit latency of the cache. */ 892810Srdreslin@umich.edu const int hitLatency; 902810Srdreslin@umich.edu 912810Srdreslin@umich.edu /** Array of pointers to blocks at the cache size boundaries. */ 922810Srdreslin@umich.edu FALRUBlk **cacheBoundaries; 932810Srdreslin@umich.edu /** A mask for the FALRUBlk::inCache bits. */ 942810Srdreslin@umich.edu int cacheMask; 952810Srdreslin@umich.edu /** The number of different size caches being tracked. */ 962810Srdreslin@umich.edu int numCaches; 972810Srdreslin@umich.edu 982810Srdreslin@umich.edu /** The cache blocks. */ 992810Srdreslin@umich.edu FALRUBlk *blks; 1002810Srdreslin@umich.edu 1012810Srdreslin@umich.edu /** The MRU block. */ 1022810Srdreslin@umich.edu FALRUBlk *head; 1032810Srdreslin@umich.edu /** The LRU block. */ 1042810Srdreslin@umich.edu FALRUBlk *tail; 1052810Srdreslin@umich.edu 1062810Srdreslin@umich.edu /** Hash table type mapping addresses to cache block pointers. */ 1072810Srdreslin@umich.edu typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; 1082810Srdreslin@umich.edu /** Iterator into the address hash table. */ 1092810Srdreslin@umich.edu typedef hash_t::const_iterator tagIterator; 1102810Srdreslin@umich.edu 1112810Srdreslin@umich.edu /** The address hash table. */ 1122810Srdreslin@umich.edu hash_t tagHash; 1132810Srdreslin@umich.edu 1142810Srdreslin@umich.edu /** 1152810Srdreslin@umich.edu * Find the cache block for the given address. 1162810Srdreslin@umich.edu * @param addr The address to find. 1172810Srdreslin@umich.edu * @return The cache block of the address, if any. 1182810Srdreslin@umich.edu */ 1192810Srdreslin@umich.edu FALRUBlk * hashLookup(Addr addr) const; 1202810Srdreslin@umich.edu 1212810Srdreslin@umich.edu /** 1222810Srdreslin@umich.edu * Move a cache block to the MRU position. 1232810Srdreslin@umich.edu * @param blk The block to promote. 1242810Srdreslin@umich.edu */ 1252810Srdreslin@umich.edu void moveToHead(FALRUBlk *blk); 1262810Srdreslin@umich.edu 1272810Srdreslin@umich.edu /** 1282810Srdreslin@umich.edu * Check to make sure all the cache boundaries are still where they should 1292810Srdreslin@umich.edu * be. Used for debugging. 1302810Srdreslin@umich.edu * @return True if everything is correct. 1312810Srdreslin@umich.edu */ 1322810Srdreslin@umich.edu bool check(); 1332810Srdreslin@umich.edu 1342810Srdreslin@umich.edu /** 1352810Srdreslin@umich.edu * @defgroup FALRUStats Fully Associative LRU specific statistics 1362810Srdreslin@umich.edu * The FA lru stack lets us track multiple cache sizes at once. These 1372810Srdreslin@umich.edu * statistics track the hits and misses for different cache sizes. 1382810Srdreslin@umich.edu * @{ 1392810Srdreslin@umich.edu */ 1402810Srdreslin@umich.edu 1412810Srdreslin@umich.edu /** Hits in each cache size >= 128K. */ 1422810Srdreslin@umich.edu Stats::Vector<> hits; 1432810Srdreslin@umich.edu /** Misses in each cache size >= 128K. */ 1442810Srdreslin@umich.edu Stats::Vector<> misses; 1452810Srdreslin@umich.edu /** Total number of accesses. */ 1462810Srdreslin@umich.edu Stats::Scalar<> accesses; 1472810Srdreslin@umich.edu 1482810Srdreslin@umich.edu /** 1492810Srdreslin@umich.edu * @} 1502810Srdreslin@umich.edu */ 1512810Srdreslin@umich.edu 1522810Srdreslin@umich.edupublic: 1532810Srdreslin@umich.edu /** 1542810Srdreslin@umich.edu * Construct and initialize this cache tagstore. 1552810Srdreslin@umich.edu * @param blkSize The block size of the cache. 1562810Srdreslin@umich.edu * @param size The size of the cache. 1572810Srdreslin@umich.edu * @param hit_latency The hit latency of the cache. 1582810Srdreslin@umich.edu */ 1592810Srdreslin@umich.edu FALRU(int blkSize, int size, int hit_latency); 1602810Srdreslin@umich.edu 1612810Srdreslin@umich.edu /** 1622810Srdreslin@umich.edu * Register the stats for this object. 1632810Srdreslin@umich.edu * @param name The name to prepend to the stats name. 1642810Srdreslin@umich.edu */ 1652810Srdreslin@umich.edu void regStats(const std::string &name); 1662810Srdreslin@umich.edu 1672810Srdreslin@umich.edu /** 1682810Srdreslin@umich.edu * Return true if the address is found in the cache. 1692810Srdreslin@umich.edu * @param asid The address space ID. 1702810Srdreslin@umich.edu * @param addr The address to look for. 1712810Srdreslin@umich.edu * @return True if the address is in the cache. 1722810Srdreslin@umich.edu */ 1732991Srdreslin@umich.edu bool probe(Addr addr) const; 1742810Srdreslin@umich.edu 1752810Srdreslin@umich.edu /** 1763862Sstever@eecs.umich.edu * Invalidate a cache block. 1773862Sstever@eecs.umich.edu * @param blk The block to invalidate. 1782810Srdreslin@umich.edu */ 1793862Sstever@eecs.umich.edu void invalidateBlk(BlkType *blk); 1802810Srdreslin@umich.edu 1812810Srdreslin@umich.edu /** 1822810Srdreslin@umich.edu * Find the block in the cache and update the replacement data. Returns 1832810Srdreslin@umich.edu * the access latency and the in cache flags as a side effect 1842810Srdreslin@umich.edu * @param addr The address to look for. 1852810Srdreslin@umich.edu * @param asid The address space ID. 1862810Srdreslin@umich.edu * @param lat The latency of the access. 1872810Srdreslin@umich.edu * @param inCache The FALRUBlk::inCache flags. 1882810Srdreslin@umich.edu * @return Pointer to the cache block. 1892810Srdreslin@umich.edu */ 1902991Srdreslin@umich.edu FALRUBlk* findBlock(Addr addr, int &lat, int *inCache = 0); 1912810Srdreslin@umich.edu 1922810Srdreslin@umich.edu /** 1932810Srdreslin@umich.edu * Find the block in the cache, do not update the replacement data. 1942810Srdreslin@umich.edu * @param addr The address to look for. 1952810Srdreslin@umich.edu * @param asid The address space ID. 1962810Srdreslin@umich.edu * @return Pointer to the cache block. 1972810Srdreslin@umich.edu */ 1982991Srdreslin@umich.edu FALRUBlk* findBlock(Addr addr) const; 1992810Srdreslin@umich.edu 2002810Srdreslin@umich.edu /** 2012810Srdreslin@umich.edu * Find a replacement block for the address provided. 2022982Sstever@eecs.umich.edu * @param pkt The request to a find a replacement candidate for. 2032810Srdreslin@umich.edu * @param writebacks List for any writebacks to be performed. 2042810Srdreslin@umich.edu * @param compress_blocks List of blocks to compress, for adaptive comp. 2052810Srdreslin@umich.edu * @return The block to place the replacement in. 2062810Srdreslin@umich.edu */ 2073349Sbinkertn@umich.edu FALRUBlk* findReplacement(PacketPtr &pkt, PacketList & writebacks, 2082810Srdreslin@umich.edu BlkList &compress_blocks); 2092810Srdreslin@umich.edu 2102810Srdreslin@umich.edu /** 2112810Srdreslin@umich.edu * Return the hit latency of this cache. 2122810Srdreslin@umich.edu * @return The hit latency. 2132810Srdreslin@umich.edu */ 2142810Srdreslin@umich.edu int getHitLatency() const 2152810Srdreslin@umich.edu { 2162810Srdreslin@umich.edu return hitLatency; 2172810Srdreslin@umich.edu } 2182810Srdreslin@umich.edu 2192810Srdreslin@umich.edu /** 2202810Srdreslin@umich.edu * Return the block size of this cache. 2212810Srdreslin@umich.edu * @return The block size. 2222810Srdreslin@umich.edu */ 2232810Srdreslin@umich.edu int getBlockSize() 2242810Srdreslin@umich.edu { 2252810Srdreslin@umich.edu return blkSize; 2262810Srdreslin@umich.edu } 2272810Srdreslin@umich.edu 2282810Srdreslin@umich.edu /** 2292810Srdreslin@umich.edu * Return the subblock size of this cache, always the block size. 2302810Srdreslin@umich.edu * @return The block size. 2312810Srdreslin@umich.edu */ 2322810Srdreslin@umich.edu int getSubBlockSize() 2332810Srdreslin@umich.edu { 2342810Srdreslin@umich.edu return blkSize; 2352810Srdreslin@umich.edu } 2362810Srdreslin@umich.edu 2372810Srdreslin@umich.edu /** 2382810Srdreslin@umich.edu * Align an address to the block size. 2392810Srdreslin@umich.edu * @param addr the address to align. 2402810Srdreslin@umich.edu * @return The aligned address. 2412810Srdreslin@umich.edu */ 2422810Srdreslin@umich.edu Addr blkAlign(Addr addr) const 2432810Srdreslin@umich.edu { 2442810Srdreslin@umich.edu return (addr & ~(Addr)(blkSize-1)); 2452810Srdreslin@umich.edu } 2462810Srdreslin@umich.edu 2472810Srdreslin@umich.edu /** 2482810Srdreslin@umich.edu * Generate the tag from the addres. For fully associative this is just the 2492810Srdreslin@umich.edu * block address. 2502810Srdreslin@umich.edu * @param addr The address to get the tag from. 2512810Srdreslin@umich.edu * @param blk ignored here 2522810Srdreslin@umich.edu * @return The tag. 2532810Srdreslin@umich.edu */ 2542810Srdreslin@umich.edu Addr extractTag(Addr addr, FALRUBlk *blk) const 2552810Srdreslin@umich.edu { 2562810Srdreslin@umich.edu return blkAlign(addr); 2572810Srdreslin@umich.edu } 2582810Srdreslin@umich.edu 2592810Srdreslin@umich.edu /** 2602810Srdreslin@umich.edu * Return the set of an address. Only one set in a fully associative cache. 2612810Srdreslin@umich.edu * @param addr The address to get the set from. 2622810Srdreslin@umich.edu * @return 0. 2632810Srdreslin@umich.edu */ 2642810Srdreslin@umich.edu int extractSet(Addr addr) const 2652810Srdreslin@umich.edu { 2662810Srdreslin@umich.edu return 0; 2672810Srdreslin@umich.edu } 2682810Srdreslin@umich.edu 2692810Srdreslin@umich.edu /** 2702810Srdreslin@umich.edu * Calculate the block offset of an address. 2712810Srdreslin@umich.edu * @param addr the address to get the offset of. 2722810Srdreslin@umich.edu * @return the block offset. 2732810Srdreslin@umich.edu */ 2742810Srdreslin@umich.edu int extractBlkOffset(Addr addr) const 2752810Srdreslin@umich.edu { 2762810Srdreslin@umich.edu return (addr & (Addr)(blkSize-1)); 2772810Srdreslin@umich.edu } 2782810Srdreslin@umich.edu 2792810Srdreslin@umich.edu /** 2802810Srdreslin@umich.edu * Regenerate the block address from the tag and the set. 2812810Srdreslin@umich.edu * @param tag The tag of the block. 2822810Srdreslin@umich.edu * @param set The set the block belongs to. 2832810Srdreslin@umich.edu * @return the block address. 2842810Srdreslin@umich.edu */ 2852810Srdreslin@umich.edu Addr regenerateBlkAddr(Addr tag, int set) const 2862810Srdreslin@umich.edu { 2872810Srdreslin@umich.edu return (tag); 2882810Srdreslin@umich.edu } 2892810Srdreslin@umich.edu 2902810Srdreslin@umich.edu /** 2912810Srdreslin@umich.edu * Read the data out of the internal storage of a cache block. FALRU 2922810Srdreslin@umich.edu * currently doesn't support data storage. 2932810Srdreslin@umich.edu * @param blk The cache block to read. 2942810Srdreslin@umich.edu * @param data The buffer to read the data into. 2952810Srdreslin@umich.edu * @return The data from the cache block. 2962810Srdreslin@umich.edu */ 2972810Srdreslin@umich.edu void readData(FALRUBlk *blk, uint8_t *data) 2982810Srdreslin@umich.edu { 2992810Srdreslin@umich.edu } 3002810Srdreslin@umich.edu 3012810Srdreslin@umich.edu /** 3022810Srdreslin@umich.edu * Write data into the internal storage of a cache block. FALRU 3032810Srdreslin@umich.edu * currently doesn't support data storage. 3042810Srdreslin@umich.edu * @param blk The cache block to be written. 3052810Srdreslin@umich.edu * @param data The data to write. 3062810Srdreslin@umich.edu * @param size The number of bytes to write. 3072810Srdreslin@umich.edu * @param writebacks A list for any writebacks to be performed. May be 3082810Srdreslin@umich.edu * needed when writing to a compressed block. 3092810Srdreslin@umich.edu */ 3102810Srdreslin@umich.edu void writeData(FALRUBlk *blk, uint8_t *data, int size, 3112814Srdreslin@umich.edu PacketList &writebacks) 3122810Srdreslin@umich.edu { 3132810Srdreslin@umich.edu } 3142810Srdreslin@umich.edu}; 3152810Srdreslin@umich.edu 3162810Srdreslin@umich.edu#endif 317