fa_lru.hh revision 6817:5aec45d0fc24
1/* 2 * Copyright (c) 2003-2005 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Erik Hallnor 29 */ 30 31/** 32 * @file 33 * Declaration of a fully associative LRU tag store. 34 */ 35 36#ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ 37#define __MEM_CACHE_TAGS_FA_LRU_HH__ 38 39#include <list> 40 41#include "base/hashmap.hh" 42#include "mem/cache/blk.hh" 43#include "mem/cache/tags/base.hh" 44#include "mem/packet.hh" 45 46/** 47 * A fully associative cache block. 48 */ 49class FALRUBlk : public CacheBlk 50{ 51public: 52 /** The previous block in LRU order. */ 53 FALRUBlk *prev; 54 /** The next block in LRU order. */ 55 FALRUBlk *next; 56 /** Has this block been touched? */ 57 bool isTouched; 58 59 /** 60 * A bit mask of the sizes of cache that this block is resident in. 61 * Each bit represents a power of 2 in MB size cache. 62 * If bit 0 is set, this block is in a 1MB cache 63 * If bit 2 is set, this block is in a 4MB cache, etc. 64 * There is one bit for each cache smaller than the full size (default 65 * 16MB). 66 */ 67 int inCache; 68}; 69 70/** 71 * A fully associative LRU cache. Keeps statistics for accesses to a number of 72 * cache sizes at once. 73 */ 74class FALRU : public BaseTags 75{ 76 public: 77 /** Typedef the block type used in this class. */ 78 typedef FALRUBlk BlkType; 79 /** Typedef a list of pointers to the local block type. */ 80 typedef std::list<FALRUBlk*> BlkList; 81 82 protected: 83 /** The block size of the cache. */ 84 const unsigned blkSize; 85 /** The size of the cache. */ 86 const unsigned size; 87 /** The number of blocks in the cache. */ 88 const unsigned numBlks; // calculated internally 89 /** The hit latency of the cache. */ 90 const unsigned hitLatency; 91 92 /** Array of pointers to blocks at the cache size boundaries. */ 93 FALRUBlk **cacheBoundaries; 94 /** A mask for the FALRUBlk::inCache bits. */ 95 int cacheMask; 96 /** The number of different size caches being tracked. */ 97 unsigned numCaches; 98 99 /** The cache blocks. */ 100 FALRUBlk *blks; 101 102 /** The MRU block. */ 103 FALRUBlk *head; 104 /** The LRU block. */ 105 FALRUBlk *tail; 106 107 /** Hash table type mapping addresses to cache block pointers. */ 108 typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; 109 /** Iterator into the address hash table. */ 110 typedef hash_t::const_iterator tagIterator; 111 112 /** The address hash table. */ 113 hash_t tagHash; 114 115 /** 116 * Find the cache block for the given address. 117 * @param addr The address to find. 118 * @return The cache block of the address, if any. 119 */ 120 FALRUBlk * hashLookup(Addr addr) const; 121 122 /** 123 * Move a cache block to the MRU position. 124 * @param blk The block to promote. 125 */ 126 void moveToHead(FALRUBlk *blk); 127 128 /** 129 * Check to make sure all the cache boundaries are still where they should 130 * be. Used for debugging. 131 * @return True if everything is correct. 132 */ 133 bool check(); 134 135 /** 136 * @defgroup FALRUStats Fully Associative LRU specific statistics 137 * The FA lru stack lets us track multiple cache sizes at once. These 138 * statistics track the hits and misses for different cache sizes. 139 * @{ 140 */ 141 142 /** Hits in each cache size >= 128K. */ 143 Stats::Vector hits; 144 /** Misses in each cache size >= 128K. */ 145 Stats::Vector misses; 146 /** Total number of accesses. */ 147 Stats::Scalar accesses; 148 149 /** 150 * @} 151 */ 152 153public: 154 /** 155 * Construct and initialize this cache tagstore. 156 * @param blkSize The block size of the cache. 157 * @param size The size of the cache. 158 * @param hit_latency The hit latency of the cache. 159 */ 160 FALRU(unsigned blkSize, unsigned size, unsigned hit_latency); 161 162 /** 163 * Register the stats for this object. 164 * @param name The name to prepend to the stats name. 165 */ 166 void regStats(const std::string &name); 167 168 /** 169 * Invalidate a cache block. 170 * @param blk The block to invalidate. 171 */ 172 void invalidateBlk(BlkType *blk); 173 174 /** 175 * Access block and update replacement data. May not succeed, in which case 176 * NULL pointer is returned. This has all the implications of a cache 177 * access and should only be used as such. 178 * Returns the access latency and inCache flags as a side effect. 179 * @param addr The address to look for. 180 * @param asid The address space ID. 181 * @param lat The latency of the access. 182 * @param inCache The FALRUBlk::inCache flags. 183 * @return Pointer to the cache block. 184 */ 185 FALRUBlk* accessBlock(Addr addr, int &lat, int context_src, int *inCache = 0); 186 187 /** 188 * Find the block in the cache, do not update the replacement data. 189 * @param addr The address to look for. 190 * @param asid The address space ID. 191 * @return Pointer to the cache block. 192 */ 193 FALRUBlk* findBlock(Addr addr) const; 194 195 /** 196 * Find a replacement block for the address provided. 197 * @param pkt The request to a find a replacement candidate for. 198 * @param writebacks List for any writebacks to be performed. 199 * @return The block to place the replacement in. 200 */ 201 FALRUBlk* findVictim(Addr addr, PacketList & writebacks); 202 203 void insertBlock(Addr addr, BlkType *blk, int context_src); 204 205 /** 206 * Return the hit latency of this cache. 207 * @return The hit latency. 208 */ 209 int getHitLatency() const 210 { 211 return hitLatency; 212 } 213 214 /** 215 * Return the block size of this cache. 216 * @return The block size. 217 */ 218 unsigned 219 getBlockSize() const 220 { 221 return blkSize; 222 } 223 224 /** 225 * Return the subblock size of this cache, always the block size. 226 * @return The block size. 227 */ 228 unsigned 229 getSubBlockSize() const 230 { 231 return blkSize; 232 } 233 234 /** 235 * Align an address to the block size. 236 * @param addr the address to align. 237 * @return The aligned address. 238 */ 239 Addr blkAlign(Addr addr) const 240 { 241 return (addr & ~(Addr)(blkSize-1)); 242 } 243 244 /** 245 * Generate the tag from the addres. For fully associative this is just the 246 * block address. 247 * @param addr The address to get the tag from. 248 * @return The tag. 249 */ 250 Addr extractTag(Addr addr) const 251 { 252 return blkAlign(addr); 253 } 254 255 /** 256 * Return the set of an address. Only one set in a fully associative cache. 257 * @param addr The address to get the set from. 258 * @return 0. 259 */ 260 int extractSet(Addr addr) const 261 { 262 return 0; 263 } 264 265 /** 266 * Calculate the block offset of an address. 267 * @param addr the address to get the offset of. 268 * @return the block offset. 269 */ 270 int extractBlkOffset(Addr addr) const 271 { 272 return (addr & (Addr)(blkSize-1)); 273 } 274 275 /** 276 * Regenerate the block address from the tag and the set. 277 * @param tag The tag of the block. 278 * @param set The set the block belongs to. 279 * @return the block address. 280 */ 281 Addr regenerateBlkAddr(Addr tag, int set) const 282 { 283 return (tag); 284 } 285}; 286 287#endif // __MEM_CACHE_TAGS_FA_LRU_HH__ 288