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 __FA_LRU_HH__ 37#define __FA_LRU_HH__ 38 39#include <list> 40 41#include "mem/cache/cache_blk.hh" 42#include "mem/packet.hh" 43#include "base/hashmap.hh" 44#include "mem/cache/tags/base_tags.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 protected: 82 /** The block size of the cache. */ 83 const int blkSize; 84 /** The size of the cache. */ 85 const int size; 86 /** The number of blocks in the cache. */ 87 const int numBlks; // calculated internally 88 /** The hit latency of the cache. */ 89 const int hitLatency; 90 91 /** Array of pointers to blocks at the cache size boundaries. */ 92 FALRUBlk **cacheBoundaries; 93 /** A mask for the FALRUBlk::inCache bits. */ 94 int cacheMask; 95 /** The number of different size caches being tracked. */ 96 int numCaches; 97 98 /** The cache blocks. */ 99 FALRUBlk *blks; 100 101 /** The MRU block. */ 102 FALRUBlk *head; 103 /** The LRU block. */ 104 FALRUBlk *tail; 105 106 /** Hash table type mapping addresses to cache block pointers. */ 107 typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; 108 /** Iterator into the address hash table. */ 109 typedef hash_t::const_iterator tagIterator; 110 111 /** The address hash table. */ 112 hash_t tagHash; 113 114 /** 115 * Find the cache block for the given address. 116 * @param addr The address to find. 117 * @return The cache block of the address, if any. 118 */ 119 FALRUBlk * hashLookup(Addr addr) const; 120 121 /** 122 * Move a cache block to the MRU position. 123 * @param blk The block to promote. 124 */ 125 void moveToHead(FALRUBlk *blk); 126 127 /** 128 * Check to make sure all the cache boundaries are still where they should 129 * be. Used for debugging. 130 * @return True if everything is correct. 131 */ 132 bool check(); 133 134 /** 135 * @defgroup FALRUStats Fully Associative LRU specific statistics 136 * The FA lru stack lets us track multiple cache sizes at once. These 137 * statistics track the hits and misses for different cache sizes. 138 * @{ 139 */ 140 141 /** Hits in each cache size >= 128K. */ 142 Stats::Vector<> hits; 143 /** Misses in each cache size >= 128K. */ 144 Stats::Vector<> misses; 145 /** Total number of accesses. */ 146 Stats::Scalar<> accesses; 147 148 /** 149 * @} 150 */ 151 152public: 153 /** 154 * Construct and initialize this cache tagstore. 155 * @param blkSize The block size of the cache. 156 * @param size The size of the cache. 157 * @param hit_latency The hit latency of the cache. 158 */ 159 FALRU(int blkSize, int size, int hit_latency); 160 161 /** 162 * Register the stats for this object. 163 * @param name The name to prepend to the stats name. 164 */ 165 void regStats(const std::string &name); 166 167 /** 168 * Return true if the address is found in the cache. 169 * @param asid The address space ID. 170 * @param addr The address to look for. 171 * @return True if the address is in the cache. 172 */ 173 bool probe(int asid, Addr addr) const; 174 175 /** 176 * Invalidate the cache block that contains the given addr. 177 * @param asid The address space ID. 178 * @param addr The address to invalidate. 179 */ 180 void invalidateBlk(int asid, Addr addr); 181 182 /** 183 * Find the block in the cache and update the replacement data. Returns 184 * the access latency and the in cache flags as a side effect 185 * @param addr The address to look for. 186 * @param asid The address space ID. 187 * @param lat The latency of the access. 188 * @param inCache The FALRUBlk::inCache flags. 189 * @return Pointer to the cache block. 190 */ 191 FALRUBlk* findBlock(Addr addr, int asid, int &lat, int *inCache = 0); 192 193 /** 194 * Find the block in the cache and update the replacement data. Returns 195 * the access latency and the in cache flags as a side effect
|
196 * @param req The req whose block to find
|
196 * @param pkt The req whose block to find |
197 * @param lat The latency of the access. 198 * @param inCache The FALRUBlk::inCache flags. 199 * @return Pointer to the cache block. 200 */ 201 FALRUBlk* findBlock(Packet * &pkt, int &lat, int *inCache = 0); 202 203 /** 204 * Find the block in the cache, do not update the replacement data. 205 * @param addr The address to look for. 206 * @param asid The address space ID. 207 * @return Pointer to the cache block. 208 */ 209 FALRUBlk* findBlock(Addr addr, int asid) const; 210 211 /** 212 * Find a replacement block for the address provided.
|
213 * @param req The request to a find a replacement candidate for.
|
213 * @param pkt The request to a find a replacement candidate for. |
214 * @param writebacks List for any writebacks to be performed. 215 * @param compress_blocks List of blocks to compress, for adaptive comp. 216 * @return The block to place the replacement in. 217 */ 218 FALRUBlk* findReplacement(Packet * &pkt, PacketList & writebacks, 219 BlkList &compress_blocks); 220 221 /** 222 * Return the hit latency of this cache. 223 * @return The hit latency. 224 */ 225 int getHitLatency() const 226 { 227 return hitLatency; 228 } 229 230 /** 231 * Return the block size of this cache. 232 * @return The block size. 233 */ 234 int getBlockSize() 235 { 236 return blkSize; 237 } 238 239 /** 240 * Return the subblock size of this cache, always the block size. 241 * @return The block size. 242 */ 243 int getSubBlockSize() 244 { 245 return blkSize; 246 } 247 248 /** 249 * Align an address to the block size. 250 * @param addr the address to align. 251 * @return The aligned address. 252 */ 253 Addr blkAlign(Addr addr) const 254 { 255 return (addr & ~(Addr)(blkSize-1)); 256 } 257 258 /** 259 * Generate the tag from the addres. For fully associative this is just the 260 * block address. 261 * @param addr The address to get the tag from. 262 * @param blk ignored here 263 * @return The tag. 264 */ 265 Addr extractTag(Addr addr, FALRUBlk *blk) const 266 { 267 return blkAlign(addr); 268 } 269 270 /** 271 * Return the set of an address. Only one set in a fully associative cache. 272 * @param addr The address to get the set from. 273 * @return 0. 274 */ 275 int extractSet(Addr addr) const 276 { 277 return 0; 278 } 279 280 /** 281 * Calculate the block offset of an address. 282 * @param addr the address to get the offset of. 283 * @return the block offset. 284 */ 285 int extractBlkOffset(Addr addr) const 286 { 287 return (addr & (Addr)(blkSize-1)); 288 } 289 290 /** 291 * Regenerate the block address from the tag and the set. 292 * @param tag The tag of the block. 293 * @param set The set the block belongs to. 294 * @return the block address. 295 */ 296 Addr regenerateBlkAddr(Addr tag, int set) const 297 { 298 return (tag); 299 } 300 301 /** 302 * Read the data out of the internal storage of a cache block. FALRU 303 * currently doesn't support data storage. 304 * @param blk The cache block to read. 305 * @param data The buffer to read the data into. 306 * @return The data from the cache block. 307 */ 308 void readData(FALRUBlk *blk, uint8_t *data) 309 { 310 } 311 312 /** 313 * Write data into the internal storage of a cache block. FALRU 314 * currently doesn't support data storage. 315 * @param blk The cache block to be written. 316 * @param data The data to write. 317 * @param size The number of bytes to write. 318 * @param writebacks A list for any writebacks to be performed. May be 319 * needed when writing to a compressed block. 320 */ 321 void writeData(FALRUBlk *blk, uint8_t *data, int size, 322 PacketList &writebacks) 323 { 324 } 325 326 /** 327 * Unimplemented. Perform a cache block copy from block aligned addresses. 328 * @param source The block aligned source address. 329 * @param dest The block aligned destination adddress. 330 * @param asid The address space ID.
|
331 * @param writebacks List for any generated writeback requests.
|
331 * @param writebacks List for any generated writeback pktuests. |
332 */ 333 void doCopy(Addr source, Addr dest, int asid, PacketList &writebacks) 334 { 335 } 336 337 /** 338 * Unimplemented. 339 */ 340 void fixCopy(Packet * &pkt, PacketList &writebacks) 341 { 342 } 343 344}; 345 346#endif
|