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