sector_tags.cc (13419:aaadcfae091a) sector_tags.cc (13445:070fc4d948c0)
1/*
2 * Copyright (c) 2018 Inria
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: Daniel Carvalho
29 */
30
31/**
32 * @file
33 * Definitions of a sector tag store.
34 */
35
36#include "mem/cache/tags/sector_tags.hh"
37
38#include <cassert>
39#include <memory>
40#include <string>
41
42#include "base/intmath.hh"
43#include "base/logging.hh"
44#include "base/types.hh"
45#include "mem/cache/base.hh"
46#include "mem/cache/replacement_policies/base.hh"
47#include "mem/cache/replacement_policies/replaceable_entry.hh"
48#include "mem/cache/tags/indexing_policies/base.hh"
49
50SectorTags::SectorTags(const SectorTagsParams *p)
51 : BaseTags(p), allocAssoc(p->assoc),
52 sequentialAccess(p->sequential_access),
53 replacementPolicy(p->replacement_policy),
54 numBlocksPerSector(p->num_blocks_per_sector),
55 numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks),
56 secBlks(numSectors), sectorShift(floorLog2(blkSize)),
57 sectorMask(numBlocksPerSector - 1)
58{
59 // Check parameters
60 fatal_if(blkSize < 4 || !isPowerOf2(blkSize),
61 "Block size must be at least 4 and a power of 2");
62 fatal_if(!isPowerOf2(numBlocksPerSector),
63 "# of blocks per sector must be non-zero and a power of 2");
64}
65
66void
67SectorTags::tagsInit()
68{
69 // Initialize all blocks
70 unsigned blk_index = 0; // index into blks array
71 for (unsigned sec_blk_index = 0; sec_blk_index < numSectors;
72 sec_blk_index++)
73 {
74 // Locate next cache sector
75 SectorBlk* sec_blk = &secBlks[sec_blk_index];
76
77 // Link block to indexing policy
78 indexingPolicy->setEntry(sec_blk, sec_blk_index);
79
80 // Associate a replacement data entry to the sector
81 sec_blk->replacementData = replacementPolicy->instantiateEntry();
82
83 // Initialize all blocks in this sector
84 sec_blk->blks.resize(numBlocksPerSector);
85 for (unsigned k = 0; k < numBlocksPerSector; ++k){
86 // Select block within the set to be linked
87 SectorSubBlk*& blk = sec_blk->blks[k];
88
89 // Locate next cache block
90 blk = &blks[blk_index];
91
92 // Associate a data chunk to the block
93 blk->data = &dataBlks[blkSize*blk_index];
94
95 // Associate sector block to this block
96 blk->setSectorBlock(sec_blk);
97
98 // Associate the sector replacement data to this block
99 blk->replacementData = sec_blk->replacementData;
100
101 // Set its index and sector offset
102 blk->setSectorOffset(k);
103
104 // Update block index
105 ++blk_index;
106 }
107 }
108}
109
110void
111SectorTags::invalidate(CacheBlk *blk)
112{
113 BaseTags::invalidate(blk);
114
115 // Get block's sector
116 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
117 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
118
119 // When a block in a sector is invalidated, it does not make the tag
120 // invalid automatically, as there might be other blocks in the sector
121 // using it. The tag is invalidated only when there is a single block
122 // in the sector.
123 if (!sector_blk->isValid()) {
124 // Decrease the number of tags in use
125 tagsInUse--;
126
127 // Invalidate replacement data, as we're invalidating the sector
128 replacementPolicy->invalidate(sector_blk->replacementData);
129 }
130}
131
132CacheBlk*
133SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat)
134{
135 CacheBlk *blk = findBlock(addr, is_secure);
136
137 // Access all tags in parallel, hence one in each way. The data side
138 // either accesses all blocks in parallel, or one block sequentially on
139 // a hit. Sequential access with a miss doesn't access data.
140 tagAccesses += allocAssoc;
141 if (sequentialAccess) {
142 if (blk != nullptr) {
143 dataAccesses += 1;
144 }
145 } else {
146 dataAccesses += allocAssoc*numBlocksPerSector;
147 }
148
149 // If a cache hit
150 if (blk != nullptr) {
151 // Update number of references to accessed block
152 blk->refCount++;
153
154 // Get block's sector
155 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
156 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
157
158 // Update replacement data of accessed block, which is shared with
159 // the whole sector it belongs to
160 replacementPolicy->touch(sector_blk->replacementData);
161 }
162
163 // The tag lookup latency is the same for a hit or a miss
164 lat = lookupLatency;
165
166 return blk;
167}
168
169void
170SectorTags::insertBlock(const Addr addr, const bool is_secure,
171 const int src_master_ID, const uint32_t task_ID,
172 CacheBlk *blk)
173{
1/*
2 * Copyright (c) 2018 Inria
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: Daniel Carvalho
29 */
30
31/**
32 * @file
33 * Definitions of a sector tag store.
34 */
35
36#include "mem/cache/tags/sector_tags.hh"
37
38#include <cassert>
39#include <memory>
40#include <string>
41
42#include "base/intmath.hh"
43#include "base/logging.hh"
44#include "base/types.hh"
45#include "mem/cache/base.hh"
46#include "mem/cache/replacement_policies/base.hh"
47#include "mem/cache/replacement_policies/replaceable_entry.hh"
48#include "mem/cache/tags/indexing_policies/base.hh"
49
50SectorTags::SectorTags(const SectorTagsParams *p)
51 : BaseTags(p), allocAssoc(p->assoc),
52 sequentialAccess(p->sequential_access),
53 replacementPolicy(p->replacement_policy),
54 numBlocksPerSector(p->num_blocks_per_sector),
55 numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks),
56 secBlks(numSectors), sectorShift(floorLog2(blkSize)),
57 sectorMask(numBlocksPerSector - 1)
58{
59 // Check parameters
60 fatal_if(blkSize < 4 || !isPowerOf2(blkSize),
61 "Block size must be at least 4 and a power of 2");
62 fatal_if(!isPowerOf2(numBlocksPerSector),
63 "# of blocks per sector must be non-zero and a power of 2");
64}
65
66void
67SectorTags::tagsInit()
68{
69 // Initialize all blocks
70 unsigned blk_index = 0; // index into blks array
71 for (unsigned sec_blk_index = 0; sec_blk_index < numSectors;
72 sec_blk_index++)
73 {
74 // Locate next cache sector
75 SectorBlk* sec_blk = &secBlks[sec_blk_index];
76
77 // Link block to indexing policy
78 indexingPolicy->setEntry(sec_blk, sec_blk_index);
79
80 // Associate a replacement data entry to the sector
81 sec_blk->replacementData = replacementPolicy->instantiateEntry();
82
83 // Initialize all blocks in this sector
84 sec_blk->blks.resize(numBlocksPerSector);
85 for (unsigned k = 0; k < numBlocksPerSector; ++k){
86 // Select block within the set to be linked
87 SectorSubBlk*& blk = sec_blk->blks[k];
88
89 // Locate next cache block
90 blk = &blks[blk_index];
91
92 // Associate a data chunk to the block
93 blk->data = &dataBlks[blkSize*blk_index];
94
95 // Associate sector block to this block
96 blk->setSectorBlock(sec_blk);
97
98 // Associate the sector replacement data to this block
99 blk->replacementData = sec_blk->replacementData;
100
101 // Set its index and sector offset
102 blk->setSectorOffset(k);
103
104 // Update block index
105 ++blk_index;
106 }
107 }
108}
109
110void
111SectorTags::invalidate(CacheBlk *blk)
112{
113 BaseTags::invalidate(blk);
114
115 // Get block's sector
116 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
117 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
118
119 // When a block in a sector is invalidated, it does not make the tag
120 // invalid automatically, as there might be other blocks in the sector
121 // using it. The tag is invalidated only when there is a single block
122 // in the sector.
123 if (!sector_blk->isValid()) {
124 // Decrease the number of tags in use
125 tagsInUse--;
126
127 // Invalidate replacement data, as we're invalidating the sector
128 replacementPolicy->invalidate(sector_blk->replacementData);
129 }
130}
131
132CacheBlk*
133SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat)
134{
135 CacheBlk *blk = findBlock(addr, is_secure);
136
137 // Access all tags in parallel, hence one in each way. The data side
138 // either accesses all blocks in parallel, or one block sequentially on
139 // a hit. Sequential access with a miss doesn't access data.
140 tagAccesses += allocAssoc;
141 if (sequentialAccess) {
142 if (blk != nullptr) {
143 dataAccesses += 1;
144 }
145 } else {
146 dataAccesses += allocAssoc*numBlocksPerSector;
147 }
148
149 // If a cache hit
150 if (blk != nullptr) {
151 // Update number of references to accessed block
152 blk->refCount++;
153
154 // Get block's sector
155 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
156 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
157
158 // Update replacement data of accessed block, which is shared with
159 // the whole sector it belongs to
160 replacementPolicy->touch(sector_blk->replacementData);
161 }
162
163 // The tag lookup latency is the same for a hit or a miss
164 lat = lookupLatency;
165
166 return blk;
167}
168
169void
170SectorTags::insertBlock(const Addr addr, const bool is_secure,
171 const int src_master_ID, const uint32_t task_ID,
172 CacheBlk *blk)
173{
174 // Do common block insertion functionality
175 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk);
176
177 // Get block's sector
178 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
179 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
180
181 // When a block is inserted, the tag is only a newly used tag if the
182 // sector was not previously present in the cache.
174 // Get block's sector
175 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
176 const SectorBlk* sector_blk = sub_blk->getSectorBlock();
177
178 // When a block is inserted, the tag is only a newly used tag if the
179 // sector was not previously present in the cache.
183 // This assumes BaseTags::insertBlock does not set the valid bit.
184 if (sector_blk->isValid()) {
185 // An existing entry's replacement data is just updated
186 replacementPolicy->touch(sector_blk->replacementData);
187 } else {
188 // Increment tag counter
189 tagsInUse++;
190
191 // A new entry resets the replacement data
192 replacementPolicy->reset(sector_blk->replacementData);
193 }
180 if (sector_blk->isValid()) {
181 // An existing entry's replacement data is just updated
182 replacementPolicy->touch(sector_blk->replacementData);
183 } else {
184 // Increment tag counter
185 tagsInUse++;
186
187 // A new entry resets the replacement data
188 replacementPolicy->reset(sector_blk->replacementData);
189 }
190
191 // Do common block insertion functionality
192 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk);
194}
195
196CacheBlk*
197SectorTags::findBlock(Addr addr, bool is_secure) const
198{
199 // Extract sector tag
200 const Addr tag = extractTag(addr);
201
202 // The address can only be mapped to a specific location of a sector
203 // due to sectors being composed of contiguous-address entries
204 const Addr offset = extractSectorOffset(addr);
205
206 // Find all possible sector entries that may contain the given address
207 const std::vector<ReplaceableEntry*> entries =
208 indexingPolicy->getPossibleEntries(addr);
209
210 // Search for block
211 for (const auto& sector : entries) {
212 auto blk = static_cast<SectorBlk*>(sector)->blks[offset];
213 if (blk->getTag() == tag && blk->isValid() &&
214 blk->isSecure() == is_secure) {
215 return blk;
216 }
217 }
218
219 // Did not find block
220 return nullptr;
221}
222
223CacheBlk*
224SectorTags::findVictim(Addr addr, const bool is_secure,
225 std::vector<CacheBlk*>& evict_blks) const
226{
227 // Get possible entries to be victimized
228 const std::vector<ReplaceableEntry*> sector_entries =
229 indexingPolicy->getPossibleEntries(addr);
230
231 // Check if the sector this address belongs to has been allocated
232 Addr tag = extractTag(addr);
233 SectorBlk* victim_sector = nullptr;
234 for (const auto& sector : sector_entries) {
235 SectorBlk* sector_blk = static_cast<SectorBlk*>(sector);
236 if ((tag == sector_blk->getTag()) && sector_blk->isValid() &&
237 (is_secure == sector_blk->isSecure())){
238 victim_sector = sector_blk;
239 break;
240 }
241 }
242
243 // If the sector is not present
244 if (victim_sector == nullptr){
245 // Choose replacement victim from replacement candidates
246 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim(
247 sector_entries));
248 }
249
250 // Get the entry of the victim block within the sector
251 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)];
252
253 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and
254 // the currently existing sector is valid.
255 if ((tag == victim_sector->getTag()) &&
256 (is_secure == victim_sector->isSecure())){
257 // It would be a hit if victim was valid, and upgrades do not call
258 // findVictim, so it cannot happen
259 assert(!victim->isValid());
260 } else {
261 // The whole sector must be evicted to make room for the new sector
262 for (const auto& blk : victim_sector->blks){
263 evict_blks.push_back(blk);
264 }
265 }
266
267 return victim;
268}
269
270int
271SectorTags::extractSectorOffset(Addr addr) const
272{
273 return (addr >> sectorShift) & sectorMask;
274}
275
276Addr
277SectorTags::regenerateBlkAddr(const CacheBlk* blk) const
278{
279 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk);
280 const SectorBlk* sec_blk = blk_cast->getSectorBlock();
281 const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk);
282 return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift);
283}
284
285void
286SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
287{
288 for (SectorSubBlk& blk : blks) {
289 visitor(blk);
290 }
291}
292
293bool
294SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
295{
296 for (SectorSubBlk& blk : blks) {
297 if (visitor(blk)) {
298 return true;
299 }
300 }
301 return false;
302}
303
304SectorTags *
305SectorTagsParams::create()
306{
307 // There must be a indexing policy
308 fatal_if(!indexing_policy, "An indexing policy is required");
309
310 return new SectorTags(this);
311}
193}
194
195CacheBlk*
196SectorTags::findBlock(Addr addr, bool is_secure) const
197{
198 // Extract sector tag
199 const Addr tag = extractTag(addr);
200
201 // The address can only be mapped to a specific location of a sector
202 // due to sectors being composed of contiguous-address entries
203 const Addr offset = extractSectorOffset(addr);
204
205 // Find all possible sector entries that may contain the given address
206 const std::vector<ReplaceableEntry*> entries =
207 indexingPolicy->getPossibleEntries(addr);
208
209 // Search for block
210 for (const auto& sector : entries) {
211 auto blk = static_cast<SectorBlk*>(sector)->blks[offset];
212 if (blk->getTag() == tag && blk->isValid() &&
213 blk->isSecure() == is_secure) {
214 return blk;
215 }
216 }
217
218 // Did not find block
219 return nullptr;
220}
221
222CacheBlk*
223SectorTags::findVictim(Addr addr, const bool is_secure,
224 std::vector<CacheBlk*>& evict_blks) const
225{
226 // Get possible entries to be victimized
227 const std::vector<ReplaceableEntry*> sector_entries =
228 indexingPolicy->getPossibleEntries(addr);
229
230 // Check if the sector this address belongs to has been allocated
231 Addr tag = extractTag(addr);
232 SectorBlk* victim_sector = nullptr;
233 for (const auto& sector : sector_entries) {
234 SectorBlk* sector_blk = static_cast<SectorBlk*>(sector);
235 if ((tag == sector_blk->getTag()) && sector_blk->isValid() &&
236 (is_secure == sector_blk->isSecure())){
237 victim_sector = sector_blk;
238 break;
239 }
240 }
241
242 // If the sector is not present
243 if (victim_sector == nullptr){
244 // Choose replacement victim from replacement candidates
245 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim(
246 sector_entries));
247 }
248
249 // Get the entry of the victim block within the sector
250 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)];
251
252 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and
253 // the currently existing sector is valid.
254 if ((tag == victim_sector->getTag()) &&
255 (is_secure == victim_sector->isSecure())){
256 // It would be a hit if victim was valid, and upgrades do not call
257 // findVictim, so it cannot happen
258 assert(!victim->isValid());
259 } else {
260 // The whole sector must be evicted to make room for the new sector
261 for (const auto& blk : victim_sector->blks){
262 evict_blks.push_back(blk);
263 }
264 }
265
266 return victim;
267}
268
269int
270SectorTags::extractSectorOffset(Addr addr) const
271{
272 return (addr >> sectorShift) & sectorMask;
273}
274
275Addr
276SectorTags::regenerateBlkAddr(const CacheBlk* blk) const
277{
278 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk);
279 const SectorBlk* sec_blk = blk_cast->getSectorBlock();
280 const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk);
281 return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift);
282}
283
284void
285SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
286{
287 for (SectorSubBlk& blk : blks) {
288 visitor(blk);
289 }
290}
291
292bool
293SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
294{
295 for (SectorSubBlk& blk : blks) {
296 if (visitor(blk)) {
297 return true;
298 }
299 }
300 return false;
301}
302
303SectorTags *
304SectorTagsParams::create()
305{
306 // There must be a indexing policy
307 fatal_if(!indexing_policy, "An indexing policy is required");
308
309 return new SectorTags(this);
310}