2 * Copyright (c) 2003-2005 The Regents of The University of Michigan
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.
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.
28 * Authors: Erik Hallnor
33 * Definitions of LRU tag store.
38 #include "base/intmath.hh"
39 #include "debug/CacheRepl.hh"
40 #include "mem/cache/tags/cacheset.hh"
41 #include "mem/cache/tags/lru.hh"
42 #include "mem/cache/base.hh"
43 #include "sim/core.hh"
47 // create and initialize a LRU/MRU cache structure
48 LRU::LRU(unsigned _numSets
, unsigned _blkSize
, unsigned _assoc
,
49 unsigned _hit_latency
)
50 : numSets(_numSets
), blkSize(_blkSize
), assoc(_assoc
),
51 hitLatency(_hit_latency
)
54 if (blkSize
< 4 || !isPowerOf2(blkSize
)) {
55 fatal("Block size must be at least 4 and a power of 2");
57 if (numSets
<= 0 || !isPowerOf2(numSets
)) {
58 fatal("# of sets must be non-zero and a power of 2");
61 fatal("associativity must be greater than zero");
63 if (hitLatency
<= 0) {
64 fatal("access latency must be greater than zero");
67 blkMask
= blkSize
- 1;
68 setShift
= floorLog2(blkSize
);
69 setMask
= numSets
- 1;
70 tagShift
= setShift
+ floorLog2(numSets
);
72 /** @todo Make warmup percentage a parameter. */
73 warmupBound
= numSets
* assoc
;
75 sets
= new CacheSet
[numSets
];
76 blks
= new BlkType
[numSets
* assoc
];
77 // allocate data storage in one big chunk
78 numBlocks
= numSets
* assoc
;
79 dataBlks
= new uint8_t[numBlocks
* blkSize
];
81 unsigned blkIndex
= 0; // index into blks array
82 for (unsigned i
= 0; i
< numSets
; ++i
) {
83 sets
[i
].assoc
= assoc
;
85 sets
[i
].blks
= new BlkType
*[assoc
];
87 // link in the data blocks
88 for (unsigned j
= 0; j
< assoc
; ++j
) {
89 // locate next cache block
90 BlkType
*blk
= &blks
[blkIndex
];
91 blk
->data
= &dataBlks
[blkSize
*blkIndex
];
94 // invalidate new cache block
97 //EGH Fix Me : do we need to initialize blk?
99 // Setting the tag to j is just to prevent long chains in the hash
100 // table; won't matter because the block is invalid
103 blk
->isTouched
= false;
119 LRU::accessBlock(Addr addr
, int &lat
, int master_id
)
121 Addr tag
= extractTag(addr
);
122 unsigned set
= extractSet(addr
);
123 BlkType
*blk
= sets
[set
].findBlk(tag
);
126 // move this block to head of the MRU list
127 sets
[set
].moveToHead(blk
);
128 DPRINTF(CacheRepl
, "set %x: moving blk %x to MRU\n",
129 set
, regenerateBlkAddr(tag
, set
));
130 if (blk
->whenReady
> curTick()
131 && blk
->whenReady
- curTick() > hitLatency
) {
132 lat
= blk
->whenReady
- curTick();
142 LRU::findBlock(Addr addr
) const
144 Addr tag
= extractTag(addr
);
145 unsigned set
= extractSet(addr
);
146 BlkType
*blk
= sets
[set
].findBlk(tag
);
151 LRU::findVictim(Addr addr
, PacketList
&writebacks
)
153 unsigned set
= extractSet(addr
);
154 // grab a replacement candidate
155 BlkType
*blk
= sets
[set
].blks
[assoc
-1];
157 if (blk
->isValid()) {
158 DPRINTF(CacheRepl
, "set %x: selecting blk %x for replacement\n",
159 set
, regenerateBlkAddr(blk
->tag
, set
));
165 LRU::insertBlock(Addr addr
, BlkType
*blk
, int master_id
)
167 if (!blk
->isTouched
) {
169 blk
->isTouched
= true;
170 if (!warmedUp
&& tagsInUse
.value() >= warmupBound
) {
172 warmupCycle
= curTick();
176 // If we're replacing a block that was previously valid update
177 // stats for it. This can't be done in findBlock() because a
178 // found block might not actually be replaced there if the
179 // coherence protocol says it can't be.
180 if (blk
->isValid()) {
182 totalRefs
+= blk
->refCount
;
186 // deal with evicted block
187 assert(blk
->srcMasterId
< cache
->system
->maxMasters());
188 occupancies
[blk
->srcMasterId
]--;
191 // Set tag for new block. Caller is responsible for setting status.
192 blk
->tag
= extractTag(addr
);
194 // deal with what we are bringing in
195 assert(master_id
< cache
->system
->maxMasters());
196 occupancies
[master_id
]++;
197 blk
->srcMasterId
= master_id
;
199 unsigned set
= extractSet(addr
);
200 sets
[set
].moveToHead(blk
);
204 LRU::invalidateBlk(BlkType
*blk
)
207 if (blk
->isValid()) {
209 assert(blk
->srcMasterId
< cache
->system
->maxMasters());
210 occupancies
[blk
->srcMasterId
]--;
211 blk
->srcMasterId
= Request::invldMasterId
;
214 blk
->isTouched
= false;
215 blk
->clearLoadLocks();
217 // should be evicted before valid blocks
218 unsigned set
= blk
->set
;
219 sets
[set
].moveToTail(blk
);
226 for (int i
= 0; i
< numBlocks
; i
++){
227 blks
[i
].clearLoadLocks();
234 for (unsigned i
= 0; i
< numSets
*assoc
; ++i
) {
235 if (blks
[i
].isValid()) {
236 totalRefs
+= blks
[i
].refCount
;