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 */
| 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;
| 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 */
| 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);
| 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 */
| 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);
| 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(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 */
| 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(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;
| 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(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 pktuests.
332 */
| 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(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 pktuests.
332 */
|
333 void doCopy(Addr source, Addr dest, int asid, PacketList &writebacks)
| 333 void doCopy(Addr source, Addr dest, PacketList &writebacks)
|
334 {
335 }
336
337 /**
338 * Unimplemented.
339 */
340 void fixCopy(Packet * &pkt, PacketList &writebacks)
341 {
342 }
343
344};
345
346#endif
| 334 {
335 }
336
337 /**
338 * Unimplemented.
339 */
340 void fixCopy(Packet * &pkt, PacketList &writebacks)
341 {
342 }
343
344};
345
346#endif
|