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 base set associative compressed superblocks tag store.
34 */
35
36#include "mem/cache/tags/compressed_tags.hh"
37
38#include "base/trace.hh"
39#include "debug/CacheComp.hh"
40#include "mem/cache/replacement_policies/base.hh"
41#include "mem/cache/replacement_policies/replaceable_entry.hh"
42#include "mem/cache/tags/indexing_policies/base.hh"
43#include "mem/packet.hh"
44#include "params/CompressedTags.hh"
45
46CompressedTags::CompressedTags(const Params *p)
47    : SectorTags(p)
48{
49}
50
51void
52CompressedTags::tagsInit()
53{
54    // Create blocks and superblocks
55    blks = std::vector<CompressionBlk>(numBlocks);
56    superBlks = std::vector<SuperBlk>(numSectors);
57
58    // Initialize all blocks
59    unsigned blk_index = 0;          // index into blks array
60    for (unsigned superblock_index = 0; superblock_index < numSectors;
61         superblock_index++)
62    {
63        // Locate next cache superblock
64        SuperBlk* superblock = &superBlks[superblock_index];
65
66        // Superblocks must be aware of the block size due to their co-
67        // allocation conditions
68        superblock->setBlkSize(blkSize);
69
70        // Associate a replacement data entry to the block
71        superblock->replacementData = replacementPolicy->instantiateEntry();
72
73        // Initialize all blocks in this superblock
74        superblock->blks.resize(numBlocksPerSector, nullptr);
75        for (unsigned k = 0; k < numBlocksPerSector; ++k){
76            // Select block within the set to be linked
77            SectorSubBlk*& blk = superblock->blks[k];
78
79            // Locate next cache block
80            blk = &blks[blk_index];
81
82            // Associate a data chunk to the block
83            blk->data = &dataBlks[blkSize*blk_index];
84
85            // Associate superblock to this block
86            blk->setSectorBlock(superblock);
87
88            // Associate the superblock replacement data to this block
89            blk->replacementData = superblock->replacementData;
90
91            // Set its index and sector offset
92            blk->setSectorOffset(k);
93
94            // Update block index
95            ++blk_index;
96        }
97
98        // Link block to indexing policy
99        indexingPolicy->setEntry(superblock, superblock_index);
100    }
101}
102
103CacheBlk*
104CompressedTags::findVictim(Addr addr, const bool is_secure,
105                           const std::size_t compressed_size,
106                           std::vector<CacheBlk*>& evict_blks) const
107{
108    // Get all possible locations of this superblock
109    const std::vector<ReplaceableEntry*> superblock_entries =
110        indexingPolicy->getPossibleEntries(addr);
111
112    // Check if the superblock this address belongs to has been allocated. If
113    // so, try co-allocating
114    Addr tag = extractTag(addr);
115    SuperBlk* victim_superblock = nullptr;
116    bool is_co_allocation = false;
117    const uint64_t offset = extractSectorOffset(addr);
118    for (const auto& entry : superblock_entries){
119        SuperBlk* superblock = static_cast<SuperBlk*>(entry);
120        if ((tag == superblock->getTag()) && superblock->isValid() &&
121            (is_secure == superblock->isSecure()) &&
122            !superblock->blks[offset]->isValid() &&
123            superblock->isCompressed() &&
124            superblock->canCoAllocate(compressed_size))
125        {
126            victim_superblock = superblock;
127            is_co_allocation = true;
128            break;
129        }
130    }
131
132    // If the superblock is not present or cannot be co-allocated a
133    // superblock must be replaced
134    if (victim_superblock == nullptr){
135        // Choose replacement victim from replacement candidates
136        victim_superblock = static_cast<SuperBlk*>(
137            replacementPolicy->getVictim(superblock_entries));
138
139        // The whole superblock must be evicted to make room for the new one
140        for (const auto& blk : victim_superblock->blks){
141            evict_blks.push_back(blk);
142        }
143    }
144
145    // Get the location of the victim block within the superblock
146    SectorSubBlk* victim = victim_superblock->blks[offset];
147
148    // It would be a hit if victim was valid in a co-allocation, and upgrades
149    // do not call findVictim, so it cannot happen
150    if (is_co_allocation){
151        assert(!victim->isValid());
152
153        // Print all co-allocated blocks
154        DPRINTF(CacheComp, "Co-Allocation: offset %d with blocks\n", offset);
155        for (const auto& blk : victim_superblock->blks){
156            if (blk->isValid()) {
157                DPRINTFR(CacheComp, "\t[%s]\n", blk->print());
158            }
159        }
160    }
161
162    return victim;
163}
164
165void
166CompressedTags::insertBlock(const PacketPtr pkt, CacheBlk *blk)
167{
168    // We check if block can co-allocate before inserting, because this check
169    // assumes the block is still invalid
170    CompressionBlk* compression_blk = static_cast<CompressionBlk*>(blk);
171    const SuperBlk* superblock = static_cast<const SuperBlk*>(
172        compression_blk->getSectorBlock());
173    const bool is_co_allocatable = superblock->isCompressed() &&
174        superblock->canCoAllocate(compression_blk->getSizeBits());
175
176    // Insert block
177    SectorTags::insertBlock(pkt, blk);
178
179    // We always store compressed blocks when possible
180    if (is_co_allocatable) {
181        compression_blk->setCompressed();
182    } else {
183        compression_blk->setUncompressed();
184    }
185}
186
187void
188CompressedTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
189{
190    for (CompressionBlk& blk : blks) {
191        visitor(blk);
192    }
193}
194
195bool
196CompressedTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
197{
198    for (CompressionBlk& blk : blks) {
199        if (visitor(blk)) {
200            return true;
201        }
202    }
203    return false;
204}
205
206CompressedTags *
207CompressedTagsParams::create()
208{
209    return new CompressedTags(this);
210}
211