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.
353 Addr extractTag(Addr addr) const
355 return (addr >> tagShift);
359 * Return the set, always 0 for IIC.
362 int extractSet(Addr addr) const
368 * Get the block offset of an address.
369 * @param addr The address to get the offset of.
370 * @return the block offset of the address.
372 int extractBlkOffset(Addr addr) const
374 return (addr & blkMask);
378 * Align an address to the block size.
379 * @param addr the address to align.
380 * @return The block address.
382 Addr blkAlign(Addr addr) const
384 return (addr & ~(Addr)blkMask);
388 * Check for the address in the tagstore.
389 * @param asid The address space ID.
390 * @param addr The address to find.
391 * @return true if it is found.
393 bool probe(Addr addr) const;
396 * Swap the position of two tags.
397 * @param index1 The first tag location.
398 * @param index2 The second tag location.
400 void tagSwap(unsigned long index1, unsigned long index2);
403 * Clear the reference bit of the tag and return its old value.
404 * @param index The pointer of the tag to manipulate.
405 * @return The previous state of the reference bit.
407 bool clearRef(unsigned long index)
409 bool tmp = tagStore[index].isReferenced();
410 tagStore[index].status &= ~BlkReferenced;
415 * Invalidate a block.
416 * @param blk The block to invalidate.
418 void invalidateBlk(BlkType *blk);
421 * Find the block and update the replacement data. This call also returns
422 * the access latency as a side effect.
423 * @param addr The address to find.
424 * @param asid The address space ID.
425 * @param lat The access latency.
426 * @return A pointer to the block found, if any.
428 IICTag* findBlock(Addr addr, int &lat);
431 * Find the block, do not update the replacement data.
432 * @param addr The address to find.
433 * @param asid The address space ID.
434 * @return A pointer to the block found, if any.
436 IICTag* findBlock(Addr addr) const;
439 * Find a replacement block for the address provided.
440 * @param pkt The request to a find a replacement candidate for.
441 * @param writebacks List for any writebacks to be performed.
442 * @return The block to place the replacement in.
444 IICTag* findReplacement(Addr addr, PacketList &writebacks);
447 * Read the data from the internal storage of the given cache block.
448 * @param blk The block to read the data from.
449 * @param data The buffer to read the data into.
450 * @return The cache block's data.
452 void readData(IICTag *blk, uint8_t *data);
455 * Write the data into the internal storage of the given cache block.
456 * @param blk The block to write to.
457 * @param data The data to write.
458 * @param size The number of bytes to write.
459 * @param writebacks A list for any writebacks to be performed. May be
460 * needed when writing to a compressed block.
462 void writeData(IICTag *blk, uint8_t *data, int size,
463 PacketList & writebacks);
466 * Called at end of simulation to complete average block reference stats.
468 virtual void cleanupRefs();
471 * Return the hash of the address.
472 * @param addr The address to hash.
473 * @return the hash of the address.
475 unsigned hash(Addr addr) const;
478 * Search for a block in the secondary tag store. Returns the number of
479 * hash lookups as a side effect.
480 * @param asid The address space ID.
481 * @param tag The tag to match.
482 * @param chain_ptr The first entry to search.
483 * @param depth The number of hash lookups made while searching.
484 * @return A pointer to the block if found.
486 IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
490 * Free the resources associated with the next replacement block.
491 * @param writebacks A list of any writebacks to perform.
493 void freeReplacementBlock(PacketList & writebacks);
496 * Return the pointer to a free data block.
497 * @param writebacks A list of any writebacks to perform.
498 * @return A pointer to a free data block.
500 unsigned long getFreeDataBlock(PacketList & writebacks);
503 * Get a free tag in the given hash set.
504 * @param set The hash set to search.
505 * @param writebacks A list of any writebacks to perform.
506 * @return a pointer to a free tag.
508 IICTag* getFreeTag(int set, PacketList & writebacks);
511 * Free the resources associated with the given tag.
512 * @param tag_ptr The tag to free.
514 void freeTag(IICTag *tag_ptr);
517 * Mark the given data block as being available.
518 * @param data_ptr The data block to free.
520 void freeDataBlock(unsigned long data_ptr);