ruby: Ruby support for sparse memory

The patch includes direct support for the MI example protocol.

1 files changed, 425 insertions, 0 deletions

diff --git a/src/mem/ruby/system/SparseMemory.cc b/src/mem/ruby/system/SparseMemory.cc
new file mode 100644
index 000000000..c351f9e60
--- /dev/null
+++ b/src/mem/ruby/system/SparseMemory.cc
@@ -0,0 +1,425 @@
+
+/*
+ * Copyright (c) 2009 Advanced Micro Devices, Inc.
+ * 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 "mem/ruby/system/SparseMemory.hh"
+
+
+// ****************************************************************
+
+
+SparseMemory::SparseMemory(int number_of_bits, int number_of_levels)
+{
+    int even_level_bits;
+    int extra;
+    m_total_number_of_bits = number_of_bits;
+    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;
+    
+    m_total_adds = 0;
+    m_total_removes = 0;
+    m_adds_per_level = new uint64_t[m_number_of_levels];
+    m_removes_per_level = new uint64_t[m_number_of_levels];
+    for (int level = 0; level < m_number_of_levels; level++) {
+        m_adds_per_level[level] = 0;
+        m_removes_per_level[level] = 0;
+    }
+}
+
+SparseMemory::~SparseMemory()
+{
+    recursivelyRemoveTables(m_map_head, 0);
+    delete m_map_head;
+    delete [] m_number_of_bits_per_level;
+    delete [] m_adds_per_level;
+    delete [] m_removes_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_t* entryStruct = &((*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;
+            nextTable = (SparseMapType*)(entryStruct->entry);
+            recursivelyRemoveTables(nextTable, (curLevel + 1));
+            delete nextTable;
+            
+        } else {
+            //
+            // If at the last level, delete the directory entry
+            //
+            Directory_Entry* dirEntry;
+            dirEntry = (Directory_Entry*)(entryStruct->entry);
+            delete dirEntry;
+        }
+        entryStruct->entry = NULL;
+    }  
+    
+    //
+    // Once all entries have been deleted, erase the entries
+    //
+    curTable->erase(curTable->begin(), curTable->end());
+}
+
+
+// PUBLIC METHODS
+
+// 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));
+    DEBUG_EXPR(CACHE_COMP, HighPrio, 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));
+        
+        DEBUG_EXPR(CACHE_COMP, HighPrio, level);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, lowBit);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, highBit - 1);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, 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]).entry);
+        } else {
+            DEBUG_MSG(CACHE_COMP, HighPrio, "Not found");
+            return false;
+        }
+    }
+    
+    DEBUG_MSG(CACHE_COMP, HighPrio, "Entry found");
+    return true;
+}
+
+// add an address to memory
+void 
+SparseMemory::add(const Address& address)
+{
+    assert(address == line_address(address));
+    assert(!exist(address));
+    
+    m_total_adds++;
+    
+    Address curAddress;
+    SparseMapType* curTable = m_map_head;
+    SparseMemEntry_t* entryStruct = 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;
+    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]).entry);
+        } 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)) {
+                Directory_Entry* tempDirEntry = new Directory_Entry();
+                tempDirEntry->getDataBlk().clear();
+                newEntry = (void*)tempDirEntry;
+            } else {
+                SparseMapType* tempMap = new SparseMapType;
+                newEntry = (void*)(tempMap);
+            }
+
+            //
+            // Create the pointer container SparseMemEntry_t and add it to the 
+            // table.
+            //
+            entryStruct = new SparseMemEntry_t;
+            entryStruct->entry = newEntry;
+            (*curTable)[curAddress] = *entryStruct;
+            
+            //
+            // 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_t* entryStruct;
+    
+    //
+    // 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));
+    
+    DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.level);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.lowBit);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.highBit - 1);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curAddress);
+    
+    assert(curInfo.curTable->count(curAddress) != 0);
+    
+    entryStruct = &((*(curInfo.curTable))[curAddress]);
+    
+    if (curInfo.level < (m_number_of_levels - 1)) {
+        //
+        // set up next level's info
+        //
+        nextInfo.curTable = (SparseMapType*)(entryStruct->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;
+            entryStruct->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.
+        //
+        Directory_Entry* dirEntry;
+        dirEntry = (Directory_Entry*)(entryStruct->entry);
+        entryStruct->entry = NULL;
+        delete dirEntry;
+        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
+Directory_Entry* 
+SparseMemory::lookup(const Address& address)
+{
+    assert(exist(address));
+    assert(address == line_address(address));
+
+    DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+    
+    Address curAddress;
+    SparseMapType* curTable = m_map_head;
+    Directory_Entry* 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));
+        
+        DEBUG_EXPR(CACHE_COMP, HighPrio, level);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, lowBit);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, highBit - 1);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, curAddress);
+        
+        //
+        // Adjust the highBit value for the next level
+        //
+        highBit -= m_number_of_bits_per_level[level];
+        
+        //
+        // The entry should be in the table and valid
+        //
+        curTable = (SparseMapType*)(((*curTable)[curAddress]).entry);
+        assert(curTable != NULL);
+    }
+    
+    //
+    // The last entry actually points to the Directory entry not a table
+    //
+    entry = (Directory_Entry*)curTable;
+
+    return entry;
+}
+
+void 
+SparseMemory::print(ostream& out) const
+{
+}
+
+void 
+SparseMemory::printStats(ostream& out) const
+{
+    out << "total_adds: " << m_total_adds << " [";
+    for (int level = 0; level < m_number_of_levels; level++) {
+        out << m_adds_per_level[level] << " ";
+    }
+    out << "]" << endl;
+    out << "total_removes: " << m_total_removes << " [";
+    for (int level = 0; level < m_number_of_levels; level++) {
+        out << m_removes_per_level[level] << " ";
+    }
+    out << "]" << endl;
+}