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 / numBlocksPerSector),
56      sectorShift(floorLog2(blkSize)), 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::tagsInit()
67{
68    // Create blocks and sector blocks
69    blks = std::vector<SectorSubBlk>(numBlocks);
70    secBlks = std::vector<SectorBlk>(numSectors);
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        // 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        // Link block to indexing policy
109        indexingPolicy->setEntry(sec_blk, sec_blk_index);
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 a cache hit
153    if (blk != nullptr) {
154        // Update number of references to accessed block
155        blk->refCount++;
156
157        // Get block's sector
158        SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
159        const SectorBlk* sector_blk = sub_blk->getSectorBlock();
160
161        // Update replacement data of accessed block, which is shared with
162        // the whole sector it belongs to
163        replacementPolicy->touch(sector_blk->replacementData);
164    }
165
166    // The tag lookup latency is the same for a hit or a miss
167    lat = lookupLatency;
168
169    return blk;
170}
171
172void
173SectorTags::insertBlock(const PacketPtr pkt, CacheBlk *blk)
174{
175    // Get block's sector
176    SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
177    const SectorBlk* sector_blk = sub_blk->getSectorBlock();
178
179    // When a block is inserted, the tag is only a newly used tag if the
180    // sector was not previously present in the cache.
181    if (sector_blk->isValid()) {
182        // An existing entry's replacement data is just updated
183        replacementPolicy->touch(sector_blk->replacementData);
184    } else {
185        // Increment tag counter
186        tagsInUse++;
187
188        // A new entry resets the replacement data
189        replacementPolicy->reset(sector_blk->replacementData);
190    }
191
192    // Do common block insertion functionality
193    BaseTags::insertBlock(pkt, 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, const std::size_t size,
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}
312