| /* | |
| * Copyright (c) 2009 Advanced Micro Devices, Inc. | |
| * Copyright (c) 2012 Mark D. Hill and David A. Wood | |
| * All rights reserved. | |
| * | |
| * Redistribution and use in source and binary forms, with or without | |
| * modification, are permitted provided that the following conditions are | |
| * met: redistributions of source code must retain the above copyright | |
| * notice, this list of conditions and the following disclaimer; | |
| * redistributions in binary form must reproduce the above copyright | |
| * notice, this list of conditions and the following disclaimer in the | |
| * documentation and/or other materials provided with the distribution; | |
| * neither the name of the copyright holders nor the names of its | |
| * contributors may be used to endorse or promote products derived from | |
| * this software without specific prior written permission. | |
| * | |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| */ | |
| #include <queue> | |
| #include "debug/RubyCache.hh" | |
| #include "mem/ruby/system/SparseMemory.hh" | |
| #include "mem/ruby/system/System.hh" | |
| using namespace std; | |
| SparseMemory::SparseMemory(int number_of_levels) | |
| { | |
| int even_level_bits; | |
| int extra; | |
| m_total_number_of_bits = RubySystem::getMemorySizeBits() | |
| - RubySystem::getBlockSizeBits();; | |
| m_number_of_levels = number_of_levels; | |
| // | |
| // Create the array that describes the bits per level | |
| // | |
| m_number_of_bits_per_level = new int[m_number_of_levels]; | |
| even_level_bits = m_total_number_of_bits / m_number_of_levels; | |
| extra = m_total_number_of_bits % m_number_of_levels; | |
| for (int level = 0; level < m_number_of_levels; level++) { | |
| if (level < extra) | |
| m_number_of_bits_per_level[level] = even_level_bits + 1; | |
| else | |
| m_number_of_bits_per_level[level] = even_level_bits; | |
| } | |
| m_map_head = new SparseMapType; | |
| } | |
| SparseMemory::~SparseMemory() | |
| { | |
| recursivelyRemoveTables(m_map_head, 0); | |
| delete m_map_head; | |
| delete [] m_number_of_bits_per_level; | |
| } | |
| // Recursively search table hierarchy for the lowest level table. | |
| // Delete the lowest table first, the tables above | |
| void | |
| SparseMemory::recursivelyRemoveTables(SparseMapType* curTable, int curLevel) | |
| { | |
| SparseMapType::iterator iter; | |
| for (iter = curTable->begin(); iter != curTable->end(); iter++) { | |
| SparseMemEntry entry = (*iter).second; | |
| if (curLevel != (m_number_of_levels - 1)) { | |
| // If the not at the last level, analyze those lower level | |
| // tables first, then delete those next tables | |
| SparseMapType* nextTable = (SparseMapType*)(entry); | |
| recursivelyRemoveTables(nextTable, (curLevel + 1)); | |
| delete nextTable; | |
| } else { | |
| // If at the last level, delete the directory entry | |
| delete (AbstractEntry*)(entry); | |
| } | |
| entry = NULL; | |
| } | |
| // Once all entries have been deleted, erase the entries | |
| curTable->erase(curTable->begin(), curTable->end()); | |
| } | |
| // tests to see if an address is present in the memory | |
| bool | |
| SparseMemory::exist(const Address& address) const | |
| { | |
| SparseMapType* curTable = m_map_head; | |
| Address curAddress; | |
| // Initiallize the high bit to be the total number of bits plus | |
| // the block offset. However the highest bit index is one less | |
| // than this value. | |
| int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits(); | |
| int lowBit; | |
| assert(address == line_address(address)); | |
| DPRINTF(RubyCache, "address: %s\n", address); | |
| for (int level = 0; level < m_number_of_levels; level++) { | |
| // Create the appropriate sub address for this level | |
| // Note: that set Address is inclusive of the specified range, | |
| // thus the high bit is one less than the total number of bits | |
| // used to create the address. | |
| lowBit = highBit - m_number_of_bits_per_level[level]; | |
| curAddress.setAddress(address.bitSelect(lowBit, highBit - 1)); | |
| DPRINTF(RubyCache, "level: %d, lowBit: %d, highBit - 1: %d, " | |
| "curAddress: %s\n", | |
| level, lowBit, highBit - 1, curAddress); | |
| // Adjust the highBit value for the next level | |
| highBit -= m_number_of_bits_per_level[level]; | |
| // If the address is found, move on to the next level. | |
| // Otherwise, return not found | |
| if (curTable->count(curAddress) != 0) { | |
| curTable = (SparseMapType*)((*curTable)[curAddress]); | |
| } else { | |
| DPRINTF(RubyCache, "Not found\n"); | |
| return false; | |
| } | |
| } | |
| DPRINTF(RubyCache, "Entry found\n"); | |
| return true; | |
| } | |
| // add an address to memory | |
| void | |
| SparseMemory::add(const Address& address, AbstractEntry* entry) | |
| { | |
| assert(address == line_address(address)); | |
| assert(!exist(address)); | |
| m_total_adds++; | |
| Address curAddress; | |
| SparseMapType* curTable = m_map_head; | |
| // Initiallize the high bit to be the total number of bits plus | |
| // the block offset. However the highest bit index is one less | |
| // than this value. | |
| int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits(); | |
| int lowBit; | |
| void* newEntry = NULL; | |
| for (int level = 0; level < m_number_of_levels; level++) { | |
| // create the appropriate address for this level | |
| // Note: that set Address is inclusive of the specified range, | |
| // thus the high bit is one less than the total number of bits | |
| // used to create the address. | |
| lowBit = highBit - m_number_of_bits_per_level[level]; | |
| curAddress.setAddress(address.bitSelect(lowBit, highBit - 1)); | |
| // Adjust the highBit value for the next level | |
| highBit -= m_number_of_bits_per_level[level]; | |
| // if the address exists in the cur table, move on. Otherwise | |
| // create a new table. | |
| if (curTable->count(curAddress) != 0) { | |
| curTable = (SparseMapType*)((*curTable)[curAddress]); | |
| } else { | |
| m_adds_per_level[level]++; | |
| // if the last level, add a directory entry. Otherwise add a map. | |
| if (level == (m_number_of_levels - 1)) { | |
| entry->getDataBlk().clear(); | |
| newEntry = (void*)entry; | |
| } else { | |
| SparseMapType* tempMap = new SparseMapType; | |
| newEntry = (void*)(tempMap); | |
| } | |
| // Create the pointer container SparseMemEntry and add it | |
| // to the table. | |
| (*curTable)[curAddress] = newEntry; | |
| // Move to the next level of the heirarchy | |
| curTable = (SparseMapType*)newEntry; | |
| } | |
| } | |
| assert(exist(address)); | |
| return; | |
| } | |
| // recursively search table hierarchy for the lowest level table. | |
| // remove the lowest entry and any empty tables above it. | |
| int | |
| SparseMemory::recursivelyRemoveLevels(const Address& address, | |
| CurNextInfo& curInfo) | |
| { | |
| Address curAddress; | |
| CurNextInfo nextInfo; | |
| SparseMemEntry entry; | |
| // create the appropriate address for this level | |
| // Note: that set Address is inclusive of the specified range, | |
| // thus the high bit is one less than the total number of bits | |
| // used to create the address. | |
| curAddress.setAddress(address.bitSelect(curInfo.lowBit, | |
| curInfo.highBit - 1)); | |
| DPRINTF(RubyCache, "address: %s, curInfo.level: %d, curInfo.lowBit: %d, " | |
| "curInfo.highBit - 1: %d, curAddress: %s\n", | |
| address, curInfo.level, curInfo.lowBit, | |
| curInfo.highBit - 1, curAddress); | |
| assert(curInfo.curTable->count(curAddress) != 0); | |
| entry = (*(curInfo.curTable))[curAddress]; | |
| if (curInfo.level < (m_number_of_levels - 1)) { | |
| // set up next level's info | |
| nextInfo.curTable = (SparseMapType*)(entry); | |
| nextInfo.level = curInfo.level + 1; | |
| nextInfo.highBit = curInfo.highBit - | |
| m_number_of_bits_per_level[curInfo.level]; | |
| nextInfo.lowBit = curInfo.lowBit - | |
| m_number_of_bits_per_level[curInfo.level + 1]; | |
| // recursively search the table hierarchy | |
| int tableSize = recursivelyRemoveLevels(address, nextInfo); | |
| // If this table below is now empty, we must delete it and | |
| // erase it from our table. | |
| if (tableSize == 0) { | |
| m_removes_per_level[curInfo.level]++; | |
| delete nextInfo.curTable; | |
| entry = NULL; | |
| curInfo.curTable->erase(curAddress); | |
| } | |
| } else { | |
| // if this is the last level, we have reached the Directory | |
| // Entry and thus we should delete it including the | |
| // SparseMemEntry container struct. | |
| delete (AbstractEntry*)(entry); | |
| entry = NULL; | |
| curInfo.curTable->erase(curAddress); | |
| m_removes_per_level[curInfo.level]++; | |
| } | |
| return curInfo.curTable->size(); | |
| } | |
| // remove an entry from the table | |
| void | |
| SparseMemory::remove(const Address& address) | |
| { | |
| assert(address == line_address(address)); | |
| assert(exist(address)); | |
| m_total_removes++; | |
| CurNextInfo nextInfo; | |
| // Initialize table pointer and level value | |
| nextInfo.curTable = m_map_head; | |
| nextInfo.level = 0; | |
| // Initiallize the high bit to be the total number of bits plus | |
| // the block offset. However the highest bit index is one less | |
| // than this value. | |
| nextInfo.highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits(); | |
| nextInfo.lowBit = nextInfo.highBit - m_number_of_bits_per_level[0];; | |
| // recursively search the table hierarchy for empty tables | |
| // starting from the level 0. Note we do not check the return | |
| // value because the head table is never deleted; | |
| recursivelyRemoveLevels(address, nextInfo); | |
| assert(!exist(address)); | |
| return; | |
| } | |
| // looks an address up in memory | |
| AbstractEntry* | |
| SparseMemory::lookup(const Address& address) | |
| { | |
| assert(address == line_address(address)); | |
| Address curAddress; | |
| SparseMapType* curTable = m_map_head; | |
| AbstractEntry* entry = NULL; | |
| // Initiallize the high bit to be the total number of bits plus | |
| // the block offset. However the highest bit index is one less | |
| // than this value. | |
| int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits(); | |
| int lowBit; | |
| for (int level = 0; level < m_number_of_levels; level++) { | |
| // create the appropriate address for this level | |
| // Note: that set Address is inclusive of the specified range, | |
| // thus the high bit is one less than the total number of bits | |
| // used to create the address. | |
| lowBit = highBit - m_number_of_bits_per_level[level]; | |
| curAddress.setAddress(address.bitSelect(lowBit, highBit - 1)); | |
| DPRINTF(RubyCache, "level: %d, lowBit: %d, highBit - 1: %d, " | |
| "curAddress: %s\n", | |
| level, lowBit, highBit - 1, curAddress); | |
| // Adjust the highBit value for the next level | |
| highBit -= m_number_of_bits_per_level[level]; | |
| // If the address is found, move on to the next level. | |
| // Otherwise, return not found | |
| if (curTable->count(curAddress) != 0) { | |
| curTable = (SparseMapType*)((*curTable)[curAddress]); | |
| } else { | |
| DPRINTF(RubyCache, "Not found\n"); | |
| return NULL; | |
| } | |
| } | |
| // The last entry actually points to the Directory entry not a table | |
| entry = (AbstractEntry*)curTable; | |
| return entry; | |
| } | |
| void | |
| SparseMemory::recordBlocks(int cntrl_id, CacheRecorder* tr) const | |
| { | |
| queue<SparseMapType*> unexplored_nodes[2]; | |
| queue<physical_address_t> address_of_nodes[2]; | |
| unexplored_nodes[0].push(m_map_head); | |
| address_of_nodes[0].push(0); | |
| int parity_of_level = 0; | |
| physical_address_t address, temp_address; | |
| Address curAddress; | |
| // Initiallize the high bit to be the total number of bits plus | |
| // the block offset. However the highest bit index is one less | |
| // than this value. | |
| int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits(); | |
| int lowBit; | |
| for (int cur_level = 0; cur_level < m_number_of_levels; cur_level++) { | |
| // create the appropriate address for this level | |
| // Note: that set Address is inclusive of the specified range, | |
| // thus the high bit is one less than the total number of bits | |
| // used to create the address. | |
| lowBit = highBit - m_number_of_bits_per_level[cur_level]; | |
| while (!unexplored_nodes[parity_of_level].empty()) { | |
| SparseMapType* node = unexplored_nodes[parity_of_level].front(); | |
| unexplored_nodes[parity_of_level].pop(); | |
| address = address_of_nodes[parity_of_level].front(); | |
| address_of_nodes[parity_of_level].pop(); | |
| SparseMapType::iterator iter; | |
| for (iter = node->begin(); iter != node->end(); iter++) { | |
| SparseMemEntry entry = (*iter).second; | |
| curAddress = (*iter).first; | |
| if (cur_level != (m_number_of_levels - 1)) { | |
| // If not at the last level, put this node in the queue | |
| unexplored_nodes[1 - parity_of_level].push( | |
| (SparseMapType*)(entry)); | |
| address_of_nodes[1 - parity_of_level].push(address | | |
| (curAddress.getAddress() << lowBit)); | |
| } else { | |
| // If at the last level, add a trace record | |
| temp_address = address | (curAddress.getAddress() | |
| << lowBit); | |
| DataBlock block = ((AbstractEntry*)entry)->getDataBlk(); | |
| tr->addRecord(cntrl_id, temp_address, 0, RubyRequestType_ST, 0, | |
| block); | |
| } | |
| } | |
| } | |
| // Adjust the highBit value for the next level | |
| highBit -= m_number_of_bits_per_level[cur_level]; | |
| parity_of_level = 1 - parity_of_level; | |
| } | |
| } | |
| void | |
| SparseMemory::regStats(const string &name) | |
| { | |
| m_total_adds.name(name + ".total_adds"); | |
| m_adds_per_level | |
| .init(m_number_of_levels) | |
| .name(name + ".adds_per_level") | |
| .flags(Stats::pdf | Stats::total) | |
| ; | |
| m_total_removes.name(name + ".total_removes"); | |
| m_removes_per_level | |
| .init(m_number_of_levels) | |
| .name(name + ".removes_per_level") | |
| .flags(Stats::pdf | Stats::total) | |
| ; | |
| } |