fa_lru.cc 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 * Definitions a fully associative LRU tagstore.
34 */
35
36#include <sstream>
37
38#include <assert.h>
39
40#include "mem/cache/tags/fa_lru.hh"
41#include "base/intmath.hh"
42#include "base/misc.hh"
43
44using namespace std;
45
46FALRU::FALRU(int _blkSize, int _size, int hit_latency)
47    : blkSize(_blkSize), size(_size),
48      numBlks(size/blkSize), hitLatency(hit_latency)
49{
50    if (!isPowerOf2(blkSize))
51        fatal("cache block size (in bytes) `%d' must be a power of two",
52              blkSize);
53    if (!(hitLatency > 0))
54        fatal("Access latency in cycles must be at least one cycle");
55    if (!isPowerOf2(size))
56        fatal("Cache Size must be power of 2 for now");
57
58    // Track all cache sizes from 128K up by powers of 2
59    numCaches = floorLog2(size) - 17;
60    if (numCaches >0){
61        cacheBoundaries = new FALRUBlk *[numCaches];
62        cacheMask = (1 << numCaches) - 1;
63    } else {
64        cacheMask = 0;
65    }
66
67    warmedUp = false;
68    warmupBound = size/blkSize;
69
70    blks = new FALRUBlk[numBlks];
71    head = &(blks[0]);
72    tail = &(blks[numBlks-1]);
73
74    head->prev = NULL;
75    head->next = &(blks[1]);
76    head->inCache = cacheMask;
77
78    tail->prev = &(blks[numBlks-2]);
79    tail->next = NULL;
80    tail->inCache = 0;
81
82    int index = (1 << 17) / blkSize;
83    int j = 0;
84    int flags = cacheMask;
85    for (int i = 1; i < numBlks-1; i++) {
86        blks[i].inCache = flags;
87        if (i == index - 1){
88            cacheBoundaries[j] = &(blks[i]);
89            flags &= ~ (1<<j);
90            ++j;
91            index = index << 1;
92        }
93        blks[i].prev = &(blks[i-1]);
94        blks[i].next = &(blks[i+1]);
95        blks[i].isTouched = false;
96    }
97    assert(j == numCaches);
98    assert(index == numBlks);
99    //assert(check());
100}
101
102void
103FALRU::regStats(const string &name)
104{
105    using namespace Stats;
106    BaseTags::regStats(name);
107    hits
108        .init(numCaches+1)
109        .name(name + ".falru_hits")
110        .desc("The number of hits in each cache size.")
111        ;
112    misses
113        .init(numCaches+1)
114        .name(name + ".falru_misses")
115        .desc("The number of misses in each cache size.")
116        ;
117    accesses
118        .name(name + ".falru_accesses")
119        .desc("The number of accesses to the FA LRU cache.")
120        ;
121
122    for (int i = 0; i < numCaches+1; ++i) {
123        stringstream size_str;
124        if (i < 3){
125            size_str << (1<<(i+7)) <<"K";
126        } else {
127            size_str << (1<<(i-3)) <<"M";
128        }
129
130        hits.subname(i, size_str.str());
131        hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
132        misses.subname(i, size_str.str());
133        misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
134    }
135}
136
137FALRUBlk *
138FALRU::hashLookup(Addr addr) const
139{
140    tagIterator iter = tagHash.find(addr);
141    if (iter != tagHash.end()) {
142        return (*iter).second;
143    }
144    return NULL;
145}
146
147bool
148FALRU::probe(Addr addr) const
149{
150    Addr blkAddr = blkAlign(addr);
151    FALRUBlk* blk = hashLookup(blkAddr);
152    return blk && blk->tag == blkAddr && blk->isValid();
153}
154
155void
156FALRU::invalidateBlk(Addr addr)
157{
158    Addr blkAddr = blkAlign(addr);
159    FALRUBlk* blk = (*tagHash.find(blkAddr)).second;
160    if (blk) {
161        assert(blk->tag == blkAddr);
162        blk->status = 0;
163        blk->isTouched = false;
164        tagsInUse--;
165    }
166}
167
168FALRUBlk*
169FALRU::findBlock(Addr addr, int &lat, int *inCache)
170{
171    accesses++;
172    int tmp_in_cache = 0;
173    Addr blkAddr = blkAlign(addr);
174    FALRUBlk* blk = hashLookup(blkAddr);
175
176    if (blk && blk->isValid()) {
177        assert(blk->tag == blkAddr);
178        tmp_in_cache = blk->inCache;
179        for (int i = 0; i < numCaches; i++) {
180            if (1<<i & blk->inCache) {
181                hits[i]++;
182            } else {
183                misses[i]++;
184            }
185        }
186        hits[numCaches]++;
187        if (blk != head){
188            moveToHead(blk);
189        }
190    } else {
191        blk = NULL;
192        for (int i = 0; i < numCaches+1; ++i) {
193            misses[i]++;
194        }
195    }
196    if (inCache) {
197        *inCache = tmp_in_cache;
198    }
199
200    lat = hitLatency;
201    //assert(check());
202    return blk;
203}
204
205FALRUBlk*
206FALRU::findBlock(PacketPtr &pkt, int &lat, int *inCache)
207{
208    Addr addr = pkt->getAddr();
209
210    accesses++;
211    int tmp_in_cache = 0;
212    Addr blkAddr = blkAlign(addr);
213    FALRUBlk* blk = hashLookup(blkAddr);
214
215    if (blk && blk->isValid()) {
216        assert(blk->tag == blkAddr);
217        tmp_in_cache = blk->inCache;
218        for (int i = 0; i < numCaches; i++) {
219            if (1<<i & blk->inCache) {
220                hits[i]++;
221            } else {
222                misses[i]++;
223            }
224        }
225        hits[numCaches]++;
226        if (blk != head){
227            moveToHead(blk);
228        }
229    } else {
230        blk = NULL;
231        for (int i = 0; i < numCaches+1; ++i) {
232            misses[i]++;
233        }
234    }
235    if (inCache) {
236        *inCache = tmp_in_cache;
237    }
238
239    lat = hitLatency;
240    //assert(check());
241    return blk;
242}
243
244FALRUBlk*
245FALRU::findBlock(Addr addr) const
246{
247    Addr blkAddr = blkAlign(addr);
248    FALRUBlk* blk = hashLookup(blkAddr);
249
250    if (blk && blk->isValid()) {
251        assert(blk->tag == blkAddr);
252    } else {
253        blk = NULL;
254    }
255    return blk;
256}
257
258FALRUBlk*
259FALRU::findReplacement(PacketPtr &pkt, PacketList &writebacks,
260                       BlkList &compress_blocks)
261{
262    FALRUBlk * blk = tail;
263    assert(blk->inCache == 0);
264    moveToHead(blk);
265    tagHash.erase(blk->tag);
266    tagHash[blkAlign(pkt->getAddr())] = blk;
267    if (blk->isValid()) {
268        replacements[0]++;
269    } else {
270        tagsInUse++;
271        blk->isTouched = true;
272        if (!warmedUp && tagsInUse.value() >= warmupBound) {
273            warmedUp = true;
274            warmupCycle = curTick;
275        }
276    }
277    //assert(check());
278    return blk;
279}
280
281void
282FALRU::moveToHead(FALRUBlk *blk)
283{
284    int updateMask = blk->inCache ^ cacheMask;
285    for (int i = 0; i < numCaches; i++){
286        if ((1<<i) & updateMask) {
287            cacheBoundaries[i]->inCache &= ~(1<<i);
288            cacheBoundaries[i] = cacheBoundaries[i]->prev;
289        } else if (cacheBoundaries[i] == blk) {
290            cacheBoundaries[i] = blk->prev;
291        }
292    }
293    blk->inCache = cacheMask;
294    if (blk != head) {
295        if (blk == tail){
296            assert(blk->next == NULL);
297            tail = blk->prev;
298            tail->next = NULL;
299        } else {
300            blk->prev->next = blk->next;
301            blk->next->prev = blk->prev;
302        }
303        blk->next = head;
304        blk->prev = NULL;
305        head->prev = blk;
306        head = blk;
307    }
308}
309
310bool
311FALRU::check()
312{
313    FALRUBlk* blk = head;
314    int size = 0;
315    int boundary = 1<<17;
316    int j = 0;
317    int flags = cacheMask;
318    while (blk) {
319        size += blkSize;
320        if (blk->inCache != flags) {
321            return false;
322        }
323        if (size == boundary && blk != tail) {
324            if (cacheBoundaries[j] != blk) {
325                return false;
326            }
327            flags &=~(1 << j);
328            boundary = boundary<<1;
329            ++j;
330        }
331        blk = blk->next;
332    }
333    return true;
334}
335