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