fa_lru.hh revision 5716
14776SN/A/* 26365SN/A * Copyright (c) 2003-2005 The Regents of The University of Michigan 34776SN/A * All rights reserved. 44776SN/A * 54776SN/A * Redistribution and use in source and binary forms, with or without 64776SN/A * modification, are permitted provided that the following conditions are 74776SN/A * met: redistributions of source code must retain the above copyright 84776SN/A * notice, this list of conditions and the following disclaimer; 94776SN/A * redistributions in binary form must reproduce the above copyright 104776SN/A * notice, this list of conditions and the following disclaimer in the 114776SN/A * documentation and/or other materials provided with the distribution; 124776SN/A * neither the name of the copyright holders nor the names of its 134776SN/A * contributors may be used to endorse or promote products derived from 144776SN/A * this software without specific prior written permission. 154776SN/A * 164776SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 174776SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 184776SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 194776SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 204776SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 214776SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 224776SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 234776SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 244776SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 254776SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 264776SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 274776SN/A * 286365SN/A * Authors: Erik Hallnor 294776SN/A */ 304776SN/A 316397Sgblack@eecs.umich.edu/** 326397Sgblack@eecs.umich.edu * @file 336397Sgblack@eecs.umich.edu * Declaration of a fully associative LRU tag store. 344776SN/A */ 356397Sgblack@eecs.umich.edu 364776SN/A#ifndef __FA_LRU_HH__ 374776SN/A#define __FA_LRU_HH__ 384776SN/A 396398Sgblack@eecs.umich.edu#include <list> 406397Sgblack@eecs.umich.edu 416397Sgblack@eecs.umich.edu#include "mem/cache/blk.hh" 426397Sgblack@eecs.umich.edu#include "mem/packet.hh" 436397Sgblack@eecs.umich.edu#include "base/hashmap.hh" 446365SN/A#include "mem/cache/tags/base.hh" 456398Sgblack@eecs.umich.edu 466398Sgblack@eecs.umich.edu/** 476398Sgblack@eecs.umich.edu * A fully associative cache block. 486398Sgblack@eecs.umich.edu */ 496398Sgblack@eecs.umich.educlass FALRUBlk : public CacheBlk 506398Sgblack@eecs.umich.edu{ 516398Sgblack@eecs.umich.edupublic: 526398Sgblack@eecs.umich.edu /** The previous block in LRU order. */ 536398Sgblack@eecs.umich.edu FALRUBlk *prev; 546411Sgblack@eecs.umich.edu /** The next block in LRU order. */ 556411Sgblack@eecs.umich.edu FALRUBlk *next; 566411Sgblack@eecs.umich.edu /** Has this block been touched? */ 576411Sgblack@eecs.umich.edu bool isTouched; 586411Sgblack@eecs.umich.edu 596411Sgblack@eecs.umich.edu /** 606411Sgblack@eecs.umich.edu * A bit mask of the sizes of cache that this block is resident in. 616398Sgblack@eecs.umich.edu * Each bit represents a power of 2 in MB size cache. 626411Sgblack@eecs.umich.edu * If bit 0 is set, this block is in a 1MB cache 636411Sgblack@eecs.umich.edu * If bit 2 is set, this block is in a 4MB cache, etc. 646411Sgblack@eecs.umich.edu * There is one bit for each cache smaller than the full size (default 656411Sgblack@eecs.umich.edu * 16MB). 666411Sgblack@eecs.umich.edu */ 676411Sgblack@eecs.umich.edu int inCache; 686411Sgblack@eecs.umich.edu}; 696411Sgblack@eecs.umich.edu 706411Sgblack@eecs.umich.edu/** 716411Sgblack@eecs.umich.edu * A fully associative LRU cache. Keeps statistics for accesses to a number of 726411Sgblack@eecs.umich.edu * cache sizes at once. 736411Sgblack@eecs.umich.edu */ 746411Sgblack@eecs.umich.educlass FALRU : public BaseTags 756411Sgblack@eecs.umich.edu{ 766411Sgblack@eecs.umich.edu public: 776411Sgblack@eecs.umich.edu /** Typedef the block type used in this class. */ 786411Sgblack@eecs.umich.edu typedef FALRUBlk BlkType; 796398Sgblack@eecs.umich.edu /** Typedef a list of pointers to the local block type. */ 806398Sgblack@eecs.umich.edu typedef std::list<FALRUBlk*> BlkList; 816398Sgblack@eecs.umich.edu protected: 826398Sgblack@eecs.umich.edu /** The block size of the cache. */ 836398Sgblack@eecs.umich.edu const int blkSize; 846398Sgblack@eecs.umich.edu /** The size of the cache. */ 856398Sgblack@eecs.umich.edu const int size; 866398Sgblack@eecs.umich.edu /** The number of blocks in the cache. */ 876398Sgblack@eecs.umich.edu const int numBlks; // calculated internally 886398Sgblack@eecs.umich.edu /** The hit latency of the cache. */ 896398Sgblack@eecs.umich.edu const int hitLatency; 906398Sgblack@eecs.umich.edu 916398Sgblack@eecs.umich.edu /** Array of pointers to blocks at the cache size boundaries. */ 926398Sgblack@eecs.umich.edu FALRUBlk **cacheBoundaries; 936398Sgblack@eecs.umich.edu /** A mask for the FALRUBlk::inCache bits. */ 946398Sgblack@eecs.umich.edu int cacheMask; 956398Sgblack@eecs.umich.edu /** The number of different size caches being tracked. */ 966398Sgblack@eecs.umich.edu int numCaches; 976398Sgblack@eecs.umich.edu 986398Sgblack@eecs.umich.edu /** The cache blocks. */ 996398Sgblack@eecs.umich.edu FALRUBlk *blks; 1006724Sgblack@eecs.umich.edu 1016724Sgblack@eecs.umich.edu /** The MRU block. */ 1026398Sgblack@eecs.umich.edu FALRUBlk *head; 1036398Sgblack@eecs.umich.edu /** The LRU block. */ 1046365SN/A FALRUBlk *tail; 1056365SN/A 1066397Sgblack@eecs.umich.edu /** Hash table type mapping addresses to cache block pointers. */ 1074776SN/A typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; 1086417Sgblack@eecs.umich.edu /** Iterator into the address hash table. */ 1096417Sgblack@eecs.umich.edu typedef hash_t::const_iterator tagIterator; 1106417Sgblack@eecs.umich.edu 1116417Sgblack@eecs.umich.edu /** The address hash table. */ 1126417Sgblack@eecs.umich.edu hash_t tagHash; 1136398Sgblack@eecs.umich.edu 1146417Sgblack@eecs.umich.edu /** 1155523SN/A * Find the cache block for the given address. 1166409Sgblack@eecs.umich.edu * @param addr The address to find. 1176397Sgblack@eecs.umich.edu * @return The cache block of the address, if any. 1186398Sgblack@eecs.umich.edu */ 1196398Sgblack@eecs.umich.edu FALRUBlk * hashLookup(Addr addr) const; 1206398Sgblack@eecs.umich.edu 1216410Sgblack@eecs.umich.edu /** 1226410Sgblack@eecs.umich.edu * Move a cache block to the MRU position. 1236410Sgblack@eecs.umich.edu * @param blk The block to promote. 1246410Sgblack@eecs.umich.edu */ 1256410Sgblack@eecs.umich.edu void moveToHead(FALRUBlk *blk); 1266410Sgblack@eecs.umich.edu 1276398Sgblack@eecs.umich.edu /** 1286410Sgblack@eecs.umich.edu * Check to make sure all the cache boundaries are still where they should 1296398Sgblack@eecs.umich.edu * be. Used for debugging. 1306398Sgblack@eecs.umich.edu * @return True if everything is correct. 1316410Sgblack@eecs.umich.edu */ 1326398Sgblack@eecs.umich.edu bool check(); 1336398Sgblack@eecs.umich.edu 1346398Sgblack@eecs.umich.edu /** 1356398Sgblack@eecs.umich.edu * @defgroup FALRUStats Fully Associative LRU specific statistics 1366398Sgblack@eecs.umich.edu * The FA lru stack lets us track multiple cache sizes at once. These 1376398Sgblack@eecs.umich.edu * statistics track the hits and misses for different cache sizes. 1386398Sgblack@eecs.umich.edu * @{ 1396398Sgblack@eecs.umich.edu */ 1406398Sgblack@eecs.umich.edu 1416398Sgblack@eecs.umich.edu /** Hits in each cache size >= 128K. */ 1426398Sgblack@eecs.umich.edu Stats::Vector<> hits; 1436398Sgblack@eecs.umich.edu /** Misses in each cache size >= 128K. */ 1446398Sgblack@eecs.umich.edu Stats::Vector<> misses; 1456398Sgblack@eecs.umich.edu /** Total number of accesses. */ 1466410Sgblack@eecs.umich.edu Stats::Scalar<> accesses; 1476398Sgblack@eecs.umich.edu 1486398Sgblack@eecs.umich.edu /** 1496398Sgblack@eecs.umich.edu * @} 1506398Sgblack@eecs.umich.edu */ 1516398Sgblack@eecs.umich.edu 1526398Sgblack@eecs.umich.edupublic: 1536398Sgblack@eecs.umich.edu /** 1546398Sgblack@eecs.umich.edu * Construct and initialize this cache tagstore. 1554776SN/A * @param blkSize The block size of the cache. 1566409Sgblack@eecs.umich.edu * @param size The size of the cache. 1576409Sgblack@eecs.umich.edu * @param hit_latency The hit latency of the cache. 1586409Sgblack@eecs.umich.edu */ 1596409Sgblack@eecs.umich.edu FALRU(int blkSize, int size, int hit_latency); 1606409Sgblack@eecs.umich.edu 1616409Sgblack@eecs.umich.edu /** 1626409Sgblack@eecs.umich.edu * Register the stats for this object. 1636409Sgblack@eecs.umich.edu * @param name The name to prepend to the stats name. 1646409Sgblack@eecs.umich.edu */ 1656409Sgblack@eecs.umich.edu void regStats(const std::string &name); 1666419Sgblack@eecs.umich.edu 1676419Sgblack@eecs.umich.edu /** 1686419Sgblack@eecs.umich.edu * Invalidate a cache block. 1696419Sgblack@eecs.umich.edu * @param blk The block to invalidate. 1706419Sgblack@eecs.umich.edu */ 1716409Sgblack@eecs.umich.edu void invalidateBlk(BlkType *blk); 1724776SN/A 1734776SN/A /** 1746365SN/A * Access block and update replacement data. May not succeed, in which case 1754776SN/A * NULL pointer is returned. This has all the implications of a cache 1764776SN/A * access and should only be used as such. 1774776SN/A * Returns the access latency and inCache flags as a side effect. 1784776SN/A * @param addr The address to look for. 1794776SN/A * @param asid The address space ID. 1806397Sgblack@eecs.umich.edu * @param lat The latency of the access. 1816397Sgblack@eecs.umich.edu * @param inCache The FALRUBlk::inCache flags. 1824776SN/A * @return Pointer to the cache block. 1836397Sgblack@eecs.umich.edu */ 1844776SN/A FALRUBlk* accessBlock(Addr addr, int &lat, int *inCache = 0); 185 186 /** 187 * Find the block in the cache, do not update the replacement data. 188 * @param addr The address to look for. 189 * @param asid The address space ID. 190 * @return Pointer to the cache block. 191 */ 192 FALRUBlk* findBlock(Addr addr) const; 193 194 /** 195 * Find a replacement block for the address provided. 196 * @param pkt The request to a find a replacement candidate for. 197 * @param writebacks List for any writebacks to be performed. 198 * @return The block to place the replacement in. 199 */ 200 FALRUBlk* findReplacement(Addr addr, PacketList & writebacks); 201 202 /** 203 * Return the hit latency of this cache. 204 * @return The hit latency. 205 */ 206 int getHitLatency() const 207 { 208 return hitLatency; 209 } 210 211 /** 212 * Return the block size of this cache. 213 * @return The block size. 214 */ 215 int getBlockSize() 216 { 217 return blkSize; 218 } 219 220 /** 221 * Return the subblock size of this cache, always the block size. 222 * @return The block size. 223 */ 224 int getSubBlockSize() 225 { 226 return blkSize; 227 } 228 229 /** 230 * Align an address to the block size. 231 * @param addr the address to align. 232 * @return The aligned address. 233 */ 234 Addr blkAlign(Addr addr) const 235 { 236 return (addr & ~(Addr)(blkSize-1)); 237 } 238 239 /** 240 * Generate the tag from the addres. For fully associative this is just the 241 * block address. 242 * @param addr The address to get the tag from. 243 * @return The tag. 244 */ 245 Addr extractTag(Addr addr) const 246 { 247 return blkAlign(addr); 248 } 249 250 /** 251 * Return the set of an address. Only one set in a fully associative cache. 252 * @param addr The address to get the set from. 253 * @return 0. 254 */ 255 int extractSet(Addr addr) const 256 { 257 return 0; 258 } 259 260 /** 261 * Calculate the block offset of an address. 262 * @param addr the address to get the offset of. 263 * @return the block offset. 264 */ 265 int extractBlkOffset(Addr addr) const 266 { 267 return (addr & (Addr)(blkSize-1)); 268 } 269 270 /** 271 * Regenerate the block address from the tag and the set. 272 * @param tag The tag of the block. 273 * @param set The set the block belongs to. 274 * @return the block address. 275 */ 276 Addr regenerateBlkAddr(Addr tag, int set) const 277 { 278 return (tag); 279 } 280 281 /** 282 * Read the data out of the internal storage of a cache block. FALRU 283 * currently doesn't support data storage. 284 * @param blk The cache block to read. 285 * @param data The buffer to read the data into. 286 * @return The data from the cache block. 287 */ 288 void readData(FALRUBlk *blk, uint8_t *data) 289 { 290 } 291 292 /** 293 * Write data into the internal storage of a cache block. FALRU 294 * currently doesn't support data storage. 295 * @param blk The cache block to be written. 296 * @param data The data to write. 297 * @param size The number of bytes to write. 298 * @param writebacks A list for any writebacks to be performed. May be 299 * needed when writing to a compressed block. 300 */ 301 void writeData(FALRUBlk *blk, uint8_t *data, int size, 302 PacketList &writebacks) 303 { 304 } 305}; 306 307#endif 308