fa_lru.hh revision 7612:917946898102 
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 __MEM_CACHE_TAGS_FA_LRU_HH__
37#define __MEM_CACHE_TAGS_FA_LRU_HH__
38
39#include <list>
40
41#include "base/hashmap.hh"
42#include "mem/cache/blk.hh"
43#include "mem/cache/tags/base.hh"
44#include "mem/packet.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
82  protected:
83    /** The block size of the cache. */
84    const unsigned blkSize;
85    /** The size of the cache. */
86    const unsigned size;
87    /** The hit latency of the cache. */
88    const unsigned hitLatency;
89
90    /** Array of pointers to blocks at the cache size  boundaries. */
91    FALRUBlk **cacheBoundaries;
92    /** A mask for the FALRUBlk::inCache bits. */
93    int cacheMask;
94    /** The number of different size caches being tracked. */
95    unsigned numCaches;
96
97    /** The cache blocks. */
98    FALRUBlk *blks;
99
100    /** The MRU block. */
101    FALRUBlk *head;
102    /** The LRU block. */
103    FALRUBlk *tail;
104
105    /** Hash table type mapping addresses to cache block pointers. */
106    typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t;
107    /** Iterator into the address hash table. */
108    typedef hash_t::const_iterator tagIterator;
109
110    /** The address hash table. */
111    hash_t tagHash;
112
113    /**
114     * Find the cache block for the given address.
115     * @param addr The address to find.
116     * @return The cache block of the address, if any.
117     */
118    FALRUBlk * hashLookup(Addr addr) const;
119
120    /**
121     * Move a cache block to the MRU position.
122     * @param blk The block to promote.
123     */
124    void moveToHead(FALRUBlk *blk);
125
126    /**
127     * Check to make sure all the cache boundaries are still where they should
128     * be. Used for debugging.
129     * @return True if everything is correct.
130     */
131    bool check();
132
133    /**
134     * @defgroup FALRUStats Fully Associative LRU specific statistics
135     * The FA lru stack lets us track multiple cache sizes at once. These
136     * statistics track the hits and misses for different cache sizes.
137     * @{
138     */
139
140    /** Hits in each cache size >= 128K. */
141    Stats::Vector hits;
142    /** Misses in each cache size >= 128K. */
143    Stats::Vector misses;
144    /** Total number of accesses. */
145    Stats::Scalar accesses;
146
147    /**
148     * @}
149     */
150
151public:
152    /**
153     * Construct and initialize this cache tagstore.
154     * @param blkSize The block size of the cache.
155     * @param size The size of the cache.
156     * @param hit_latency The hit latency of the cache.
157     */
158    FALRU(unsigned blkSize, unsigned size, unsigned hit_latency);
159
160    /**
161     * Register the stats for this object.
162     * @param name The name to prepend to the stats name.
163     */
164    void regStats(const std::string &name);
165
166    /**
167     * Invalidate a cache block.
168     * @param blk The block to invalidate.
169     */
170    void invalidateBlk(BlkType *blk);
171
172    /**
173     * Access block and update replacement data.  May not succeed, in which case
174     * NULL pointer is returned.  This has all the implications of a cache
175     * access and should only be used as such.
176     * Returns the access latency and inCache flags as a side effect.
177     * @param addr The address to look for.
178     * @param asid The address space ID.
179     * @param lat The latency of the access.
180     * @param inCache The FALRUBlk::inCache flags.
181     * @return Pointer to the cache block.
182     */
183    FALRUBlk* accessBlock(Addr addr, int &lat, int context_src, int *inCache = 0);
184
185    /**
186     * Find the block in the cache, do not update the replacement data.
187     * @param addr The address to look for.
188     * @param asid The address space ID.
189     * @return Pointer to the cache block.
190     */
191    FALRUBlk* findBlock(Addr addr) const;
192
193    /**
194     * Find a replacement block for the address provided.
195     * @param pkt The request to a find a replacement candidate for.
196     * @param writebacks List for any writebacks to be performed.
197     * @return The block to place the replacement in.
198     */
199    FALRUBlk* findVictim(Addr addr, PacketList & writebacks);
200
201    void insertBlock(Addr addr, BlkType *blk, int context_src);
202
203    /**
204     * Return the hit latency of this cache.
205     * @return The hit latency.
206     */
207    int getHitLatency() const
208    {
209        return hitLatency;
210    }
211
212    /**
213     * Return the block size of this cache.
214     * @return The block size.
215     */
216    unsigned
217    getBlockSize() const
218    {
219        return blkSize;
220    }
221
222    /**
223     * Return the subblock size of this cache, always the block size.
224     * @return The block size.
225     */
226    unsigned
227    getSubBlockSize() const
228    {
229        return blkSize;
230    }
231
232    /**
233     * Align an address to the block size.
234     * @param addr the address to align.
235     * @return The aligned address.
236     */
237    Addr blkAlign(Addr addr) const
238    {
239        return (addr & ~(Addr)(blkSize-1));
240    }
241
242    /**
243     * Generate the tag from the addres. For fully associative this is just the
244     * block address.
245     * @param addr The address to get the tag from.
246     * @return The tag.
247     */
248    Addr extractTag(Addr addr) const
249    {
250        return blkAlign(addr);
251    }
252
253    /**
254     * Return the set of an address. Only one set in a fully associative cache.
255     * @param addr The address to get the set from.
256     * @return 0.
257     */
258    int extractSet(Addr addr) const
259    {
260        return 0;
261    }
262
263    /**
264     * Calculate the block offset of an address.
265     * @param addr the address to get the offset of.
266     * @return the block offset.
267     */
268    int extractBlkOffset(Addr addr) const
269    {
270        return (addr & (Addr)(blkSize-1));
271    }
272
273    /**
274     * Regenerate the block address from the tag and the set.
275     * @param tag The tag of the block.
276     * @param set The set the block belongs to.
277     * @return the block address.
278     */
279    Addr regenerateBlkAddr(Addr tag, int set) const
280    {
281        return (tag);
282    }
283
284    /**
285     *iterated through all blocks and clear all locks
286     *Needed to clear all lock tracking at once
287     */
288    virtual void clearLocks();
289};
290
291#endif // __MEM_CACHE_TAGS_FA_LRU_HH__
292