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
| 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
|
66 // Link block to indexing policy
67 indexingPolicy->setEntry(superblock, superblock_index);
68
69 // Associate a replacement data entry to the block
70 superblock->replacementData = replacementPolicy->instantiateEntry();
71
72 // Initialize all blocks in this superblock
73 superblock->blks.resize(numBlocksPerSector, nullptr);
74 for (unsigned k = 0; k < numBlocksPerSector; ++k){
75 // Select block within the set to be linked
76 SectorSubBlk*& blk = superblock->blks[k];
77
78 // Locate next cache block
79 blk = &blks[blk_index];
80
81 // Associate a data chunk to the block
82 blk->data = &dataBlks[blkSize*blk_index];
83
84 // Associate superblock to this block
85 blk->setSectorBlock(superblock);
86
87 // Associate the superblock replacement data to this block
88 blk->replacementData = superblock->replacementData;
89
90 // Set its index and sector offset
91 blk->setSectorOffset(k);
92
93 // Update block index
94 ++blk_index;
95 }
96 }
97}
98
| 70 // Link block to indexing policy
71 indexingPolicy->setEntry(superblock, superblock_index);
72
73 // Associate a replacement data entry to the block
74 superblock->replacementData = replacementPolicy->instantiateEntry();
75
76 // Initialize all blocks in this superblock
77 superblock->blks.resize(numBlocksPerSector, nullptr);
78 for (unsigned k = 0; k < numBlocksPerSector; ++k){
79 // Select block within the set to be linked
80 SectorSubBlk*& blk = superblock->blks[k];
81
82 // Locate next cache block
83 blk = &blks[blk_index];
84
85 // Associate a data chunk to the block
86 blk->data = &dataBlks[blkSize*blk_index];
87
88 // Associate superblock to this block
89 blk->setSectorBlock(superblock);
90
91 // Associate the superblock replacement data to this block
92 blk->replacementData = superblock->replacementData;
93
94 // Set its index and sector offset
95 blk->setSectorOffset(k);
96
97 // Update block index
98 ++blk_index;
99 }
100 }
101}
102
|
99bool
100CompressedTags::canCoAllocate(const SuperBlk* superblock,
101 const std::size_t compressed_size) const
102{
103 // Simple co-allocation function: at most numBlocksPerSector blocks that
104 // compress at least to (100/numBlocksPerSector)% of their original size
105 // can share a superblock
106 return superblock->isCompressed() &&
107 (compressed_size <= (blkSize * 8) / numBlocksPerSector);
108}
109
| |
110CacheBlk*
111CompressedTags::findVictim(Addr addr, const bool is_secure,
112 const std::size_t compressed_size,
113 std::vector<CacheBlk*>& evict_blks) const
114{
115 // Get all possible locations of this superblock
116 const std::vector<ReplaceableEntry*> superblock_entries =
117 indexingPolicy->getPossibleEntries(addr);
118
119 // Check if the superblock this address belongs to has been allocated. If
120 // so, try co-allocating
121 Addr tag = extractTag(addr);
122 SuperBlk* victim_superblock = nullptr;
123 bool is_co_allocation = false;
124 const uint64_t offset = extractSectorOffset(addr);
125 for (const auto& entry : superblock_entries){
126 SuperBlk* superblock = static_cast<SuperBlk*>(entry);
127 if ((tag == superblock->getTag()) && superblock->isValid() &&
128 (is_secure == superblock->isSecure()) &&
129 !superblock->blks[offset]->isValid() &&
| 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() &&
|
130 canCoAllocate(superblock, compressed_size))
| 123 superblock->isCompressed() &&
124 superblock->canCoAllocate(compressed_size))
|
131 {
132 victim_superblock = superblock;
133 is_co_allocation = true;
134 break;
135 }
136 }
137
138 // If the superblock is not present or cannot be co-allocated a
139 // superblock must be replaced
140 if (victim_superblock == nullptr){
141 // Choose replacement victim from replacement candidates
142 victim_superblock = static_cast<SuperBlk*>(
143 replacementPolicy->getVictim(superblock_entries));
144
145 // The whole superblock must be evicted to make room for the new one
146 for (const auto& blk : victim_superblock->blks){
147 evict_blks.push_back(blk);
148 }
149 }
150
151 // Get the location of the victim block within the superblock
152 SectorSubBlk* victim = victim_superblock->blks[offset];
153
154 // It would be a hit if victim was valid in a co-allocation, and upgrades
155 // do not call findVictim, so it cannot happen
156 if (is_co_allocation){
157 assert(!victim->isValid());
158
159 // Print all co-allocated blocks
160 DPRINTF(CacheComp, "Co-Allocation: offset %d with blocks\n", offset);
161 for (const auto& blk : victim_superblock->blks){
162 if (blk->isValid()) {
163 DPRINTFR(CacheComp, "\t[%s]\n", blk->print());
164 }
165 }
166 }
167
168 return victim;
169}
170
171void
172CompressedTags::insertBlock(const PacketPtr pkt, CacheBlk *blk)
173{
| 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
|
174 // Insert block
175 SectorTags::insertBlock(pkt, blk);
176
| 176 // Insert block
177 SectorTags::insertBlock(pkt, blk);
178
|
177 // @todo We always store compressed blocks when possible
178 CompressionBlk* compression_blk = static_cast<CompressionBlk*>(blk);
179 compression_blk->setUncompressed();
| 179 // We always store compressed blocks when possible
180 if (is_co_allocatable) {
181 compression_blk->setCompressed();
182 } else {
183 compression_blk->setUncompressed();
184 }
|
180}
181
182void
183CompressedTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
184{
185 for (CompressionBlk& blk : blks) {
186 visitor(blk);
187 }
188}
189
190bool
191CompressedTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
192{
193 for (CompressionBlk& blk : blks) {
194 if (visitor(blk)) {
195 return true;
196 }
197 }
198 return false;
199}
200
201CompressedTags *
202CompressedTagsParams::create()
203{
204 return new CompressedTags(this);
205}
| 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}
|