fa_lru.hh revision 3349:fec4a86fa212 
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(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(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 &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 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(PacketPtr &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) const;
210
211    /**
212     * Find a replacement block for the address provided.
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(PacketPtr &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#endif
328