compressed_tags.cc revision 13946:8e96e9be7f2c
12972Sgblack@eecs.umich.edu/* 22972Sgblack@eecs.umich.edu * Copyright (c) 2018 Inria 32972Sgblack@eecs.umich.edu * All rights reserved. 42972Sgblack@eecs.umich.edu * 52972Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 62972Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 72972Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 82972Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 92972Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 102972Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 112972Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 122972Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 132972Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 142972Sgblack@eecs.umich.edu * this software without specific prior written permission. 152972Sgblack@eecs.umich.edu * 162972Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172972Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182972Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192972Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202972Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212972Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222972Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232972Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242972Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252972Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262972Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272972Sgblack@eecs.umich.edu * 282972Sgblack@eecs.umich.edu * Authors: Daniel Carvalho 292972Sgblack@eecs.umich.edu */ 302972Sgblack@eecs.umich.edu 312972Sgblack@eecs.umich.edu/** 322972Sgblack@eecs.umich.edu * @file 332972Sgblack@eecs.umich.edu * Definitions of a base set associative compressed superblocks tag store. 348229Snate@binkert.org */ 354040Ssaidi@eecs.umich.edu 366215Snate@binkert.org#include "mem/cache/tags/compressed_tags.hh" 372972Sgblack@eecs.umich.edu 382972Sgblack@eecs.umich.edu#include "base/trace.hh" 392972Sgblack@eecs.umich.edu#include "debug/CacheComp.hh" 402972Sgblack@eecs.umich.edu#include "mem/cache/replacement_policies/base.hh" 417741Sgblack@eecs.umich.edu#include "mem/cache/replacement_policies/replaceable_entry.hh" 427741Sgblack@eecs.umich.edu#include "mem/cache/tags/indexing_policies/base.hh" 437720Sgblack@eecs.umich.edu#include "mem/packet.hh" 447741Sgblack@eecs.umich.edu#include "params/CompressedTags.hh" 455251Sksewell@umich.edu 467741Sgblack@eecs.umich.eduCompressedTags::CompressedTags(const Params *p) 477741Sgblack@eecs.umich.edu : SectorTags(p) 482972Sgblack@eecs.umich.edu{ 492972Sgblack@eecs.umich.edu} 502972Sgblack@eecs.umich.edu 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 // 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 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() && 130 canCoAllocate(superblock, 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{ 174 // Insert block 175 SectorTags::insertBlock(pkt, blk); 176 177 // @todo We always store compressed blocks when possible 178 CompressionBlk* compression_blk = static_cast<CompressionBlk*>(blk); 179 compression_blk->setUncompressed(); 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} 206