2 * Copyright (c) 2002-2005 The Regents of The University of Michigan
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.
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.
28 * Authors: Erik Hallnor
33 * Declaration of the Indirect Index Cache (IIC) tags store.
42 #include "mem/cache/cache_blk.hh"
43 #include "mem/cache/tags/repl/repl.hh"
44 #include "mem/packet.hh"
45 #include "base/statistics.hh"
46 #include "mem/cache/tags/base_tags.hh"
48 class BaseCache; // Forward declaration
53 class IICTag : public CacheBlk
57 * Copy the contents of the given IICTag into this one.
58 * @param rhs The tag to copy.
59 * @return const reference to this tag.
61 const IICTag& operator=(const IICTag& rhs)
63 CacheBlk::operator=(rhs);
64 chain_ptr = rhs.chain_ptr;
67 trivialData = rhs.trivialData;
68 numData = rhs.numData;
70 for (int i = 0; i < rhs.numData; ++i) {
71 data_ptr.push_back(rhs.data_ptr[i]);
76 /** Hash chain pointer into secondary store. */
77 unsigned long chain_ptr;
78 /** Data array pointers for each subblock. */
79 std::vector<unsigned long> data_ptr;
80 /** Replacement Entry pointer. */
83 * An array to store small compressed data. Conceputally the same size
84 * as the unsused data array pointers.
88 * The number of allocated subblocks.
94 * A hash set for the IIC primary lookup table.
98 /** The associativity of the primary table. */
101 /** The number of hash chains followed when finding the last block. */
103 /** The current number of blocks on the chain. */
106 /** Tag pointer into the secondary tag storage. */
107 unsigned long chain_ptr;
109 /** The LRU list of the primary table. MRU is at 0 index. */
113 * Find the addr in this set, return the chain pointer to the secondary if
115 * @param asid The address space ID.
116 * @param tag The address to find.
117 * @param chain_ptr The chain pointer to start the search of the secondary
118 * @return Pointer to the tag, NULL if not found.
120 IICTag* findTag( Addr tag, unsigned long &chain_ptr)
123 for (int i = 0; i < assoc; ++i) {
124 if (tags[i]->tag == tag && tags[i]->isValid()) {
128 chain_ptr = this->chain_ptr;
133 * Find an usused tag in this set.
134 * @return Pointer to the unused tag, NULL if none are free.
138 for (int i = 0; i < assoc; ++i) {
139 if (!tags[i]->isValid()) {
147 * Move a tag to the head of the LRU list
148 * @param tag The tag to move.
150 void moveToHead(IICTag *tag);
153 * Move a tag to the tail (LRU) of the LRU list
154 * @param tag The tag to move.
156 void moveToTail(IICTag *tag);
160 * The IIC tag store. This is a hardware-realizable, fully-associative tag
161 * store that uses software replacement, e.g. Gen.
163 class IIC : public BaseTags
166 /** Typedef of the block type used in this class. */
167 typedef IICTag BlkType;
168 /** Typedef for list of pointers to the local block type. */
169 typedef std::list<IICTag*> BlkList;
171 /** The number of set in the primary table. */
173 /** The block size in bytes. */
175 /** The associativity of the primary table. */
177 /** The base hit latency. */
178 const int hitLatency;
179 /** The subblock size, used for compression. */
182 /** The number of subblocks */
184 /** The number of bytes used by data pointers */
185 const int trivialSize;
187 /** The amount to shift address to get the tag. */
189 /** The mask to get block offset bits. */
190 const unsigned blkMask;
192 /** The amount to shift to get the subblock number. */
194 /** The mask to get the correct subblock number. */
195 const unsigned subMask;
197 /** The latency of a hash lookup. */
199 /** The number of data blocks. */
201 /** The total number of tags in primary and secondary. */
203 /** The number of tags in the secondary tag store. */
204 const int numSecondary;
206 /** The Null tag pointer. */
208 /** The last tag in the primary table. */
209 const int primaryBound;
211 /** All of the tags */
214 * Pointer to the head of the secondary freelist (maintained with chain
217 unsigned long freelist;
219 * The data block freelist.
221 std::list<unsigned long> blkFreelist;
223 /** The primary table. */
226 /** The replacement policy. */
229 /** An array of data reference counters. */
230 int *dataReferenceCount;
232 /** The data blocks. */
235 /** Storage for the fast access data of each cache block. */
239 * Count of the current number of free secondary tags.
240 * Used for debugging.
246 * @addtogroup IICStatistics IIC Statistics
250 /** Hash hit depth of cache hits. */
251 Stats::Distribution<> hitHashDepth;
252 /** Hash depth for cache misses. */
253 Stats::Distribution<> missHashDepth;
254 /** Count of accesses to each hash set. */
255 Stats::Distribution<> setAccess;
257 /** The total hash depth for every miss. */
258 Stats::Scalar<> missDepthTotal;
259 /** The total hash depth for all hits. */
260 Stats::Scalar<> hitDepthTotal;
261 /** The number of hash misses. */
262 Stats::Scalar<> hashMiss;
263 /** The number of hash hits. */
264 Stats::Scalar<> hashHit;
269 * Collection of parameters for the IIC.
273 /** The size in bytes of the cache. */
275 /** The number of sets in the primary table. */
277 /** The block size in bytes. */
279 /** The associativity of the primary table. */
281 /** The number of cycles for each hash lookup. */
283 /** The number of cycles to read the data. */
285 /** The replacement policy. */
287 /** The subblock size in bytes. */
292 * Construct and initialize this tag store.
293 * @param params The IIC parameters.
295 * Should make a way to have less tags in the primary than blks in the
296 * cache. Also should be able to specify number of secondary blks.
306 * Register the statistics.
307 * @param name The name to prepend to the statistic descriptions.
309 void regStats(const std::string &name);
312 * Regenerate the block address from the tag.
313 * @param tag The tag of the block.
314 * @param set Not needed for the iic.
315 * @return The block address.
317 Addr regenerateBlkAddr(Addr tag, int set) {
318 return (((Addr)tag << tagShift));
322 * Return the block size.
323 * @return The block size.
331 * Return the subblock size.
332 * @return The subblock size.
334 int getSubBlockSize()
340 * Return the hit latency.
341 * @return the hit latency.
343 int getHitLatency() const
349 * Generate the tag from the address.
350 * @param addr The address to a get a tag for.
351 * @param blk Ignored here.
354 Addr extractTag(Addr addr, IICTag *blk) const
356 return (addr >> tagShift);
360 * Generate the tag from the address.
361 * @param addr The address to a get a tag for.
364 Addr extractTag(Addr addr) const
366 return (addr >> tagShift);
370 * Return the set, always 0 for IIC.
373 int extractSet(Addr addr) const
379 * Get the block offset of an address.
380 * @param addr The address to get the offset of.
381 * @return the block offset of the address.
383 int extractBlkOffset(Addr addr) const
385 return (addr & blkMask);
389 * Align an address to the block size.
390 * @param addr the address to align.
391 * @return The block address.
393 Addr blkAlign(Addr addr) const
395 return (addr & ~(Addr)blkMask);
399 * Check for the address in the tagstore.
400 * @param asid The address space ID.
401 * @param addr The address to find.
402 * @return true if it is found.
404 bool probe(Addr addr) const;
407 * Swap the position of two tags.
408 * @param index1 The first tag location.
409 * @param index2 The second tag location.
411 void tagSwap(unsigned long index1, unsigned long index2);
414 * Clear the reference bit of the tag and return its old value.
415 * @param index The pointer of the tag to manipulate.
416 * @return The previous state of the reference bit.
418 bool clearRef(unsigned long index)
420 bool tmp = tagStore[index].isReferenced();
421 tagStore[index].status &= ~BlkReferenced;
426 * Decompress a block if it is compressed.
427 * @param index The tag store index for the block to uncompress.
429 void decompressBlock(unsigned long index);
432 * Try and compress a block if it is not already compressed.
433 * @param index The tag store index for the block to compress.
435 void compressBlock(unsigned long index);
438 * Invalidate the block containing the address.
439 * @param asid The address space ID.
440 * @param addr The address to invalidate.
442 void invalidateBlk(Addr addr);
445 * Find the block and update the replacement data. This call also returns
446 * the access latency as a side effect.
447 * @param addr The address to find.
448 * @param asid The address space ID.
449 * @param lat The access latency.
450 * @return A pointer to the block found, if any.
452 IICTag* findBlock(Addr addr, int &lat);
455 * Find the block and update the replacement data. This call also returns
456 * the access latency as a side effect.
457 * @param pkt The req whose block to find
458 * @param lat The access latency.
459 * @return A pointer to the block found, if any.
461 IICTag* findBlock(PacketPtr &pkt, int &lat);
464 * Find the block, do not update the replacement data.
465 * @param addr The address to find.
466 * @param asid The address space ID.
467 * @return A pointer to the block found, if any.
469 IICTag* findBlock(Addr addr) const;
472 * Find a replacement block for the address provided.
473 * @param pkt The request to a find a replacement candidate for.
474 * @param writebacks List for any writebacks to be performed.
475 * @param compress_blocks List of blocks to compress, for adaptive comp.
476 * @return The block to place the replacement in.
478 IICTag* findReplacement(PacketPtr &pkt, PacketList &writebacks,
479 BlkList &compress_blocks);
482 * Read the data from the internal storage of the given cache block.
483 * @param blk The block to read the data from.
484 * @param data The buffer to read the data into.
485 * @return The cache block's data.
487 void readData(IICTag *blk, uint8_t *data);
490 * Write the data into the internal storage of the given cache block.
491 * @param blk The block to write to.
492 * @param data The data to write.
493 * @param size The number of bytes to write.
494 * @param writebacks A list for any writebacks to be performed. May be
495 * needed when writing to a compressed block.
497 void writeData(IICTag *blk, uint8_t *data, int size,
498 PacketList & writebacks);
501 * Called at end of simulation to complete average block reference stats.
503 virtual void cleanupRefs();
506 * Return the hash of the address.
507 * @param addr The address to hash.
508 * @return the hash of the address.
510 unsigned hash(Addr addr) const;
513 * Search for a block in the secondary tag store. Returns the number of
514 * hash lookups as a side effect.
515 * @param asid The address space ID.
516 * @param tag The tag to match.
517 * @param chain_ptr The first entry to search.
518 * @param depth The number of hash lookups made while searching.
519 * @return A pointer to the block if found.
521 IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
525 * Free the resources associated with the next replacement block.
526 * @param writebacks A list of any writebacks to perform.
528 void freeReplacementBlock(PacketList & writebacks);
531 * Return the pointer to a free data block.
532 * @param writebacks A list of any writebacks to perform.
533 * @return A pointer to a free data block.
535 unsigned long getFreeDataBlock(PacketList & writebacks);
538 * Get a free tag in the given hash set.
539 * @param set The hash set to search.
540 * @param writebacks A list of any writebacks to perform.
541 * @return a pointer to a free tag.
543 IICTag* getFreeTag(int set, PacketList & writebacks);
546 * Free the resources associated with the given tag.
547 * @param tag_ptr The tag to free.
549 void freeTag(IICTag *tag_ptr);
552 * Mark the given data block as being available.
553 * @param data_ptr The data block to free.
555 void freeDataBlock(unsigned long data_ptr);