fa_lru.cc revision 2811:9da12e9830ce 
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
43using namespace std;
44
45FALRU::FALRU(int _blkSize, int _size, int hit_latency)
46    : blkSize(_blkSize), size(_size),
47      numBlks(size/blkSize), hitLatency(hit_latency)
48{
49    if (!isPowerOf2(blkSize))
50        fatal("cache block size (in bytes) `%d' must be a power of two",
51              blkSize);
52    if (!(hitLatency > 0))
53        fatal("Access latency in cycles must be at least one cycle");
54    if (!isPowerOf2(size))
55        fatal("Cache Size must be power of 2 for now");
56
57    // Track all cache sizes from 128K up by powers of 2
58    numCaches = floorLog2(size) - 17;
59    if (numCaches >0){
60        cacheBoundaries = new FALRUBlk *[numCaches];
61        cacheMask = (1 << numCaches) - 1;
62    } else {
63        cacheMask = 0;
64    }
65
66    warmedUp = false;
67    warmupBound = size/blkSize;
68
69    blks = new FALRUBlk[numBlks];
70    head = &(blks[0]);
71    tail = &(blks[numBlks-1]);
72
73    head->prev = NULL;
74    head->next = &(blks[1]);
75    head->inCache = cacheMask;
76
77    tail->prev = &(blks[numBlks-2]);
78    tail->next = NULL;
79    tail->inCache = 0;
80
81    int index = (1 << 17) / blkSize;
82    int j = 0;
83    int flags = cacheMask;
84    for (int i = 1; i < numBlks-1; i++) {
85        blks[i].inCache = flags;
86        if (i == index - 1){
87            cacheBoundaries[j] = &(blks[i]);
88            flags &= ~ (1<<j);
89            ++j;
90            index = index << 1;
91        }
92        blks[i].prev = &(blks[i-1]);
93        blks[i].next = &(blks[i+1]);
94        blks[i].isTouched = false;
95    }
96    assert(j == numCaches);
97    assert(index == numBlks);
98    //assert(check());
99}
100
101void
102FALRU::regStats(const string &name)
103{
104    using namespace Stats;
105    BaseTags::regStats(name);
106    hits
107        .init(numCaches+1)
108        .name(name + ".falru_hits")
109        .desc("The number of hits in each cache size.")
110        ;
111    misses
112        .init(numCaches+1)
113        .name(name + ".falru_misses")
114        .desc("The number of misses in each cache size.")
115        ;
116    accesses
117        .name(name + ".falru_accesses")
118        .desc("The number of accesses to the FA LRU cache.")
119        ;
120
121    for (int i = 0; i < numCaches+1; ++i) {
122        stringstream size_str;
123        if (i < 3){
124            size_str << (1<<(i+7)) <<"K";
125        } else {
126            size_str << (1<<(i-3)) <<"M";
127        }
128
129        hits.subname(i, size_str.str());
130        hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
131        misses.subname(i, size_str.str());
132        misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
133    }
134}
135
136FALRUBlk *
137FALRU::hashLookup(Addr addr) const
138{
139    tagIterator iter = tagHash.find(addr);
140    if (iter != tagHash.end()) {
141        return (*iter).second;
142    }
143    return NULL;
144}
145
146bool
147FALRU::probe(int asid, Addr addr) const
148{
149    Addr blkAddr = blkAlign(addr);
150    FALRUBlk* blk = hashLookup(blkAddr);
151    return blk && blk->tag == blkAddr && blk->isValid();
152}
153
154void
155FALRU::invalidateBlk(int asid, Addr addr)
156{
157    Addr blkAddr = blkAlign(addr);
158    FALRUBlk* blk = (*tagHash.find(blkAddr)).second;
159    if (blk) {
160        assert(blk->tag == blkAddr);
161        blk->status = 0;
162        blk->isTouched = false;
163        tagsInUse--;
164    }
165}
166
167FALRUBlk*
168FALRU::findBlock(Addr addr, int asid, int &lat, int *inCache)
169{
170    accesses++;
171    int tmp_in_cache = 0;
172    Addr blkAddr = blkAlign(addr);
173    FALRUBlk* blk = hashLookup(blkAddr);
174
175    if (blk && blk->isValid()) {
176        assert(blk->tag == blkAddr);
177        tmp_in_cache = blk->inCache;
178        for (int i = 0; i < numCaches; i++) {
179            if (1<<i & blk->inCache) {
180                hits[i]++;
181            } else {
182                misses[i]++;
183            }
184        }
185        hits[numCaches]++;
186        if (blk != head){
187            moveToHead(blk);
188        }
189    } else {
190        blk = NULL;
191        for (int i = 0; i < numCaches+1; ++i) {
192            misses[i]++;
193        }
194    }
195    if (inCache) {
196        *inCache = tmp_in_cache;
197    }
198
199    lat = hitLatency;
200    //assert(check());
201    return blk;
202}
203
204FALRUBlk*
205FALRU::findBlock(Packet * &pkt, int &lat, int *inCache)
206{
207    Addr addr = pkt->paddr;
208
209    accesses++;
210    int tmp_in_cache = 0;
211    Addr blkAddr = blkAlign(addr);
212    FALRUBlk* blk = hashLookup(blkAddr);
213
214    if (blk && blk->isValid()) {
215        assert(blk->tag == blkAddr);
216        tmp_in_cache = blk->inCache;
217        for (int i = 0; i < numCaches; i++) {
218            if (1<<i & blk->inCache) {
219                hits[i]++;
220            } else {
221                misses[i]++;
222            }
223        }
224        hits[numCaches]++;
225        if (blk != head){
226            moveToHead(blk);
227        }
228    } else {
229        blk = NULL;
230        for (int i = 0; i < numCaches+1; ++i) {
231            misses[i]++;
232        }
233    }
234    if (inCache) {
235        *inCache = tmp_in_cache;
236    }
237
238    lat = hitLatency;
239    //assert(check());
240    return blk;
241}
242
243FALRUBlk*
244FALRU::findBlock(Addr addr, int asid) const
245{
246    Addr blkAddr = blkAlign(addr);
247    FALRUBlk* blk = hashLookup(blkAddr);
248
249    if (blk && blk->isValid()) {
250        assert(blk->tag == blkAddr);
251    } else {
252        blk = NULL;
253    }
254    return blk;
255}
256
257FALRUBlk*
258FALRU::findReplacement(Packet * &pkt, PacketList* &writebacks,
259                       BlkList &compress_blocks)
260{
261    FALRUBlk * blk = tail;
262    assert(blk->inCache == 0);
263    moveToHead(blk);
264    tagHash.erase(blk->tag);
265    tagHash[blkAlign(pkt->paddr)] = blk;
266    if (blk->isValid()) {
267        int req->setThreadNum() = (blk->xc) ? blk->xc->getThreadNum() : 0;
268        replacements[req->getThreadNum()]++;
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