2 * Copyright (c) 2018 Inria
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: Daniel Carvalho
33 * Definitions of a base set associative sector tag store.
36 #include "mem/cache/tags/sector_tags.hh"
42 #include "base/intmath.hh"
43 #include "base/logging.hh"
44 #include "base/types.hh"
45 #include "debug/CacheRepl.hh"
46 #include "mem/cache/base.hh"
47 #include "mem/cache/replacement_policies/base.hh"
49 SectorTags::SectorTags(const SectorTagsParams
*p
)
50 : BaseTags(p
), assoc(p
->assoc
), allocAssoc(p
->assoc
),
51 sequentialAccess(p
->sequential_access
),
52 replacementPolicy(p
->replacement_policy
),
53 numBlocksPerSector(p
->num_blocks_per_sector
),
54 numSectors(numBlocks
/ p
->num_blocks_per_sector
),
55 numSets(numSectors
/ p
->assoc
),
56 blks(numBlocks
), secBlks(numSectors
), sets(numSets
),
57 sectorShift(floorLog2(blkSize
)),
58 setShift(sectorShift
+ floorLog2(numBlocksPerSector
)),
59 tagShift(setShift
+ floorLog2(numSets
)),
60 sectorMask(numBlocksPerSector
- 1), setMask(numSets
- 1)
63 fatal_if(blkSize
< 4 || !isPowerOf2(blkSize
),
64 "Block size must be at least 4 and a power of 2");
65 fatal_if(!isPowerOf2(numSets
),
66 "# of sets must be non-zero and a power of 2");
67 fatal_if(!isPowerOf2(numBlocksPerSector
),
68 "# of blocks per sector must be non-zero and a power of 2");
69 fatal_if(assoc
<= 0, "associativity must be greater than zero");
71 // Initialize all sets
72 unsigned sec_blk_index
= 0; // index into sector blks array
73 unsigned blk_index
= 0; // index into blks array
74 for (unsigned i
= 0; i
< numSets
; ++i
) {
75 sets
[i
].resize(assoc
);
77 // Initialize all sectors in this set
78 for (unsigned j
= 0; j
< assoc
; ++j
) {
79 // Select block within the set to be linked
80 SectorBlk
*& sec_blk
= sets
[i
][j
];
82 // Locate next cache sector
83 sec_blk
= &secBlks
[sec_blk_index
];
85 // Associate a replacement data entry to the sector
86 sec_blk
->replacementData
= replacementPolicy
->instantiateEntry();
88 // Initialize all blocks in this sector
89 sec_blk
->blks
.resize(numBlocksPerSector
);
90 for (unsigned k
= 0; k
< numBlocksPerSector
; ++k
){
91 // Select block within the set to be linked
92 SectorSubBlk
*& blk
= sec_blk
->blks
[k
];
94 // Locate next cache block
95 blk
= &blks
[blk_index
];
97 // Associate a data chunk to the block
98 blk
->data
= &dataBlks
[blkSize
*blk_index
];
100 // Associate sector block to this block
101 blk
->setSectorBlock(sec_blk
);
103 // Associate the sector replacement data to this block
104 blk
->replacementData
= sec_blk
->replacementData
;
106 // Set its set, way and sector offset
109 blk
->setSectorOffset(k
);
111 // Update block index
115 // Update sector block index
122 SectorTags::invalidate(CacheBlk
*blk
)
124 BaseTags::invalidate(blk
);
126 // Get block's sector
127 SectorSubBlk
* sub_blk
= static_cast<SectorSubBlk
*>(blk
);
128 const SectorBlk
* sector_blk
= sub_blk
->getSectorBlock();
130 // When a block in a sector is invalidated, it does not make the tag
131 // invalid automatically, as there might be other blocks in the sector
132 // using it. The tag is invalidated only when there is a single block
134 if (!sector_blk
->isValid()) {
135 // Decrease the number of tags in use
138 // Invalidate replacement data, as we're invalidating the sector
139 replacementPolicy
->invalidate(sector_blk
->replacementData
);
144 SectorTags::accessBlock(Addr addr
, bool is_secure
, Cycles
&lat
)
146 CacheBlk
*blk
= findBlock(addr
, is_secure
);
148 // Access all tags in parallel, hence one in each way. The data side
149 // either accesses all blocks in parallel, or one block sequentially on
150 // a hit. Sequential access with a miss doesn't access data.
151 tagAccesses
+= allocAssoc
;
152 if (sequentialAccess
) {
153 if (blk
!= nullptr) {
157 dataAccesses
+= allocAssoc
*numBlocksPerSector
;
160 if (blk
!= nullptr) {
163 // Check if the block to be accessed is available. If not,
164 // apply the accessLatency on top of block->whenReady.
165 if (blk
->whenReady
> curTick() &&
166 cache
->ticksToCycles(blk
->whenReady
- curTick()) >
168 lat
= cache
->ticksToCycles(blk
->whenReady
- curTick()) +
172 // Update number of references to accessed block
175 // Get block's sector
176 SectorSubBlk
* sub_blk
= static_cast<SectorSubBlk
*>(blk
);
177 const SectorBlk
* sector_blk
= sub_blk
->getSectorBlock();
179 // Update replacement data of accessed block, which is shared with
180 // the whole sector it belongs to
181 replacementPolicy
->touch(sector_blk
->replacementData
);
190 const std::vector
<SectorBlk
*>
191 SectorTags::getPossibleLocations(Addr addr
) const
193 return sets
[extractSet(addr
)];
197 SectorTags::insertBlock(const PacketPtr pkt
, CacheBlk
*blk
)
200 BaseTags::insertBlock(pkt
, blk
);
202 // Get block's sector
203 SectorSubBlk
* sub_blk
= static_cast<SectorSubBlk
*>(blk
);
204 const SectorBlk
* sector_blk
= sub_blk
->getSectorBlock();
206 // When a block is inserted, the tag is only a newly used tag if the
207 // sector was not previously present in the cache.
208 // This assumes BaseTags::insertBlock does not set the valid bit.
209 if (sector_blk
->isValid()) {
210 // An existing entry's replacement data is just updated
211 replacementPolicy
->touch(sector_blk
->replacementData
);
213 // Increment tag counter
216 // A new entry resets the replacement data
217 replacementPolicy
->reset(sector_blk
->replacementData
);
222 SectorTags::findBlock(Addr addr
, bool is_secure
) const
224 // Extract sector tag
225 const Addr tag
= extractTag(addr
);
227 // The address can only be mapped to a specific location of a sector
228 // due to sectors being composed of contiguous-address entries
229 const Addr offset
= extractSectorOffset(addr
);
231 // Find all possible sector locations for the given address
232 const std::vector
<SectorBlk
*> locations
= getPossibleLocations(addr
);
235 for (const auto& sector
: locations
) {
236 auto blk
= sector
->blks
[offset
];
237 if (blk
->getTag() == tag
&& blk
->isValid() &&
238 blk
->isSecure() == is_secure
) {
243 // Did not find block
248 SectorTags::findBlockBySetAndWay(int set
, int way
) const
250 return sets
[set
][way
];
254 SectorTags::findVictim(Addr addr
, const bool is_secure
,
255 std::vector
<CacheBlk
*>& evict_blks
) const
257 // Get all possible locations of this sector
258 const std::vector
<SectorBlk
*> sector_locations
=
259 getPossibleLocations(addr
);
261 // Check if the sector this address belongs to has been allocated
262 Addr tag
= extractTag(addr
);
263 SectorBlk
* victim_sector
= nullptr;
264 for (const auto& sector
: sector_locations
){
265 if ((tag
== sector
->getTag()) && sector
->isValid() &&
266 (is_secure
== sector
->isSecure())){
267 victim_sector
= sector
;
272 // If the sector is not present
273 if (victim_sector
== nullptr){
274 // Choose replacement victim from replacement candidates
275 victim_sector
= static_cast<SectorBlk
*>(replacementPolicy
->getVictim(
276 std::vector
<ReplaceableEntry
*>(
277 sector_locations
.begin(), sector_locations
.end())));
280 // Get the location of the victim block within the sector
281 SectorSubBlk
* victim
= victim_sector
->blks
[extractSectorOffset(addr
)];
283 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and
284 // the currently existing sector is valid.
285 if ((tag
== victim_sector
->getTag()) &&
286 (is_secure
== victim_sector
->isSecure())){
287 // It would be a hit if victim was valid, and upgrades do not call
288 // findVictim, so it cannot happen
289 assert(!victim
->isValid());
291 // The whole sector must be evicted to make room for the new sector
292 for (const auto& blk
: victim_sector
->blks
){
293 evict_blks
.push_back(blk
);
297 DPRINTF(CacheRepl
, "set %x, way %x, sector offset %x: %s\n",
298 "selecting blk for replacement\n", victim
->set
, victim
->way
,
299 victim
->getSectorOffset());
305 SectorTags::extractTag(Addr addr
) const
307 return addr
>> tagShift
;
311 SectorTags::extractSet(Addr addr
) const
313 return (addr
>> setShift
) & setMask
;
317 SectorTags::extractSectorOffset(Addr addr
) const
319 return (addr
>> sectorShift
) & sectorMask
;
323 SectorTags::regenerateBlkAddr(const CacheBlk
* blk
) const
325 const SectorSubBlk
* blk_cast
= static_cast<const SectorSubBlk
*>(blk
);
326 return ((blk_cast
->getTag() << tagShift
) | ((Addr
)blk
->set
<< setShift
) |
327 ((Addr
)blk_cast
->getSectorOffset() << sectorShift
));
331 SectorTags::forEachBlk(std::function
<void(CacheBlk
&)> visitor
)
333 for (SectorSubBlk
& blk
: blks
) {
339 SectorTags::anyBlk(std::function
<bool(CacheBlk
&)> visitor
)
341 for (SectorSubBlk
& blk
: blks
) {
350 SectorTagsParams::create()
352 return new SectorTags(this);