PersistentTable.cc revision 7054
16242Sgblack@eecs.umich.edu/* 27093Sgblack@eecs.umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 37093Sgblack@eecs.umich.edu * All rights reserved. 47093Sgblack@eecs.umich.edu * 57093Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 67093Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 77093Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 87093Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 97093Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 107093Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 117093Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 127093Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 137093Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 146242Sgblack@eecs.umich.edu * this software without specific prior written permission. 156242Sgblack@eecs.umich.edu * 166242Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176242Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186242Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196242Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206242Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216242Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226242Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236242Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246242Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256242Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266242Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276242Sgblack@eecs.umich.edu */ 286242Sgblack@eecs.umich.edu 296242Sgblack@eecs.umich.edu#include "mem/gems_common/util.hh" 306242Sgblack@eecs.umich.edu#include "mem/ruby/system/PersistentTable.hh" 316242Sgblack@eecs.umich.edu 326242Sgblack@eecs.umich.edu// randomize so that handoffs are not locality-aware 336242Sgblack@eecs.umich.edu#if 0 346242Sgblack@eecs.umich.eduint persistent_randomize[] = {0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 356242Sgblack@eecs.umich.edu 10, 14, 3, 7, 11, 15}; 366242Sgblack@eecs.umich.eduint persistent_randomize[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 376242Sgblack@eecs.umich.edu 10, 11, 12, 13, 14, 15}; 386242Sgblack@eecs.umich.edu#endif 396242Sgblack@eecs.umich.edu 406242Sgblack@eecs.umich.eduPersistentTable::PersistentTable() 416242Sgblack@eecs.umich.edu{ 426242Sgblack@eecs.umich.edu m_map_ptr = new Map<Address, PersistentTableEntry>; 436242Sgblack@eecs.umich.edu} 446242Sgblack@eecs.umich.edu 456242Sgblack@eecs.umich.eduPersistentTable::~PersistentTable() 466242Sgblack@eecs.umich.edu{ 476242Sgblack@eecs.umich.edu delete m_map_ptr; 486242Sgblack@eecs.umich.edu m_map_ptr = NULL; 496242Sgblack@eecs.umich.edu} 506242Sgblack@eecs.umich.edu 516242Sgblack@eecs.umich.eduvoid 526242Sgblack@eecs.umich.eduPersistentTable::persistentRequestLock(const Address& address, 536242Sgblack@eecs.umich.edu MachineID locker, 546242Sgblack@eecs.umich.edu AccessType type) 556242Sgblack@eecs.umich.edu{ 566242Sgblack@eecs.umich.edu#if 0 576242Sgblack@eecs.umich.edu if (locker == m_chip_ptr->getID()) 586242Sgblack@eecs.umich.edu cout << "Chip " << m_chip_ptr->getID() << ": " << llocker 596242Sgblack@eecs.umich.edu << " requesting lock for " << address << endl; 606242Sgblack@eecs.umich.edu 616242Sgblack@eecs.umich.edu MachineID locker = (MachineID) persistent_randomize[llocker]; 626242Sgblack@eecs.umich.edu#endif 636242Sgblack@eecs.umich.edu 646242Sgblack@eecs.umich.edu assert(address == line_address(address)); 657111Sgblack@eecs.umich.edu if (!m_map_ptr->exist(address)) { 666242Sgblack@eecs.umich.edu // Allocate if not present 676242Sgblack@eecs.umich.edu PersistentTableEntry entry; 686242Sgblack@eecs.umich.edu entry.m_starving.add(locker); 696242Sgblack@eecs.umich.edu if (type == AccessType_Write) { 707408Sgblack@eecs.umich.edu entry.m_request_to_write.add(locker); 716735Sgblack@eecs.umich.edu } 726242Sgblack@eecs.umich.edu m_map_ptr->add(address, entry); 736242Sgblack@eecs.umich.edu } else { 746242Sgblack@eecs.umich.edu PersistentTableEntry& entry = m_map_ptr->lookup(address); 756723Sgblack@eecs.umich.edu 766242Sgblack@eecs.umich.edu // 776242Sgblack@eecs.umich.edu // Make sure we're not already in the locked set 786261Sgblack@eecs.umich.edu // 796403Sgblack@eecs.umich.edu assert(!(entry.m_starving.isElement(locker))); 806403Sgblack@eecs.umich.edu 816403Sgblack@eecs.umich.edu entry.m_starving.add(locker); 827325Sgblack@eecs.umich.edu if (type == AccessType_Write) { 837325Sgblack@eecs.umich.edu entry.m_request_to_write.add(locker); 847400SAli.Saidi@ARM.com } 857350SAli.Saidi@ARM.com assert(entry.m_marked.isSubset(entry.m_starving)); 867259Sgblack@eecs.umich.edu } 877259Sgblack@eecs.umich.edu} 887259Sgblack@eecs.umich.edu 897259Sgblack@eecs.umich.eduvoid 907264Sgblack@eecs.umich.eduPersistentTable::persistentRequestUnlock(const Address& address, 917267Sgblack@eecs.umich.edu MachineID unlocker) 927285Sgblack@eecs.umich.edu{ 937265Sgblack@eecs.umich.edu#if 0 947266Sgblack@eecs.umich.edu if (unlocker == m_chip_ptr->getID()) 957266Sgblack@eecs.umich.edu cout << "Chip " << m_chip_ptr->getID() << ": " << uunlocker 967266Sgblack@eecs.umich.edu << " requesting unlock for " << address << endl; 977268Sgblack@eecs.umich.edu 987272Sgblack@eecs.umich.edu MachineID unlocker = (MachineID) persistent_randomize[uunlocker]; 997272Sgblack@eecs.umich.edu#endif 1007271Sgblack@eecs.umich.edu 1017273Sgblack@eecs.umich.edu assert(address == line_address(address)); 1027287Sgblack@eecs.umich.edu assert(m_map_ptr->exist(address)); 1037287Sgblack@eecs.umich.edu PersistentTableEntry& entry = m_map_ptr->lookup(address); 1047274Sgblack@eecs.umich.edu 1057275Sgblack@eecs.umich.edu // 1067276Sgblack@eecs.umich.edu // Make sure we're in the locked set 1077286Sgblack@eecs.umich.edu // 1087297Sgblack@eecs.umich.edu assert(entry.m_starving.isElement(unlocker)); 1097297Sgblack@eecs.umich.edu assert(entry.m_marked.isSubset(entry.m_starving)); 1107298Sgblack@eecs.umich.edu entry.m_starving.remove(unlocker); 1117352Sgblack@eecs.umich.edu entry.m_marked.remove(unlocker); 1127352Sgblack@eecs.umich.edu entry.m_request_to_write.remove(unlocker); 1137354Sgblack@eecs.umich.edu assert(entry.m_marked.isSubset(entry.m_starving)); 1147353Sgblack@eecs.umich.edu 1157355Sgblack@eecs.umich.edu // Deallocate if empty 1167355Sgblack@eecs.umich.edu if (entry.m_starving.isEmpty()) { 1177355Sgblack@eecs.umich.edu assert(entry.m_marked.isEmpty()); 1187355Sgblack@eecs.umich.edu m_map_ptr->erase(address); 1197355Sgblack@eecs.umich.edu } 1207355Sgblack@eecs.umich.edu} 1217355Sgblack@eecs.umich.edu 1227355Sgblack@eecs.umich.edubool 1237355Sgblack@eecs.umich.eduPersistentTable::okToIssueStarving(const Address& address, 1247355Sgblack@eecs.umich.edu MachineID machId) const 1257355Sgblack@eecs.umich.edu{ 1267355Sgblack@eecs.umich.edu assert(address == line_address(address)); 1277355Sgblack@eecs.umich.edu if (!m_map_ptr->exist(address)) { 1287355Sgblack@eecs.umich.edu // No entry present 1297362Sgblack@eecs.umich.edu return true; 1307362Sgblack@eecs.umich.edu } else if (m_map_ptr->lookup(address).m_starving.isElement(machId)) { 1317362Sgblack@eecs.umich.edu // We can't issue another lockdown until are previous unlock 1327362Sgblack@eecs.umich.edu // has occurred 1337390Sgblack@eecs.umich.edu return false; 1347404SAli.Saidi@ARM.com } else { 1357404SAli.Saidi@ARM.com return m_map_ptr->lookup(address).m_marked.isEmpty(); 1367404SAli.Saidi@ARM.com } 1377404SAli.Saidi@ARM.com} 1387406SAli.Saidi@ARM.com 1397406SAli.Saidi@ARM.comMachineID 1407406SAli.Saidi@ARM.comPersistentTable::findSmallest(const Address& address) const 1417436Sdam.sunwoo@arm.com{ 1427436Sdam.sunwoo@arm.com assert(address == line_address(address)); 1437436Sdam.sunwoo@arm.com assert(m_map_ptr->exist(address)); 1447436Sdam.sunwoo@arm.com const PersistentTableEntry& entry = m_map_ptr->lookup(address); 1457436Sdam.sunwoo@arm.com return entry.m_starving.smallestElement(); 1467436Sdam.sunwoo@arm.com} 1477436Sdam.sunwoo@arm.com 1487436Sdam.sunwoo@arm.comAccessType 1497436Sdam.sunwoo@arm.comPersistentTable::typeOfSmallest(const Address& address) const 1507583SAli.Saidi@arm.com{ 1517583SAli.Saidi@arm.com assert(address == line_address(address)); 1527583SAli.Saidi@arm.com assert(m_map_ptr->exist(address)); 1537583SAli.Saidi@arm.com const PersistentTableEntry& entry = m_map_ptr->lookup(address); 1547583SAli.Saidi@arm.com if (entry.m_request_to_write. 1557583SAli.Saidi@arm.com isElement(entry.m_starving.smallestElement())) { 1567583SAli.Saidi@arm.com return AccessType_Write; 1577583SAli.Saidi@arm.com } else { 1587583SAli.Saidi@arm.com return AccessType_Read; 1597583SAli.Saidi@arm.com } 1607583SAli.Saidi@arm.com} 1617583SAli.Saidi@arm.com 1627583SAli.Saidi@arm.comvoid 1637583SAli.Saidi@arm.comPersistentTable::markEntries(const Address& address) 1647583SAli.Saidi@arm.com{ 1657583SAli.Saidi@arm.com assert(address == line_address(address)); 1667259Sgblack@eecs.umich.edu if (m_map_ptr->exist(address)) { 1677406SAli.Saidi@ARM.com PersistentTableEntry& entry = m_map_ptr->lookup(address); 1687259Sgblack@eecs.umich.edu 1697259Sgblack@eecs.umich.edu // None should be marked 1707259Sgblack@eecs.umich.edu assert(entry.m_marked.isEmpty()); 1717259Sgblack@eecs.umich.edu 1727259Sgblack@eecs.umich.edu // Mark all the nodes currently in the table 1737259Sgblack@eecs.umich.edu entry.m_marked = entry.m_starving; 1747259Sgblack@eecs.umich.edu } 1757259Sgblack@eecs.umich.edu} 1767259Sgblack@eecs.umich.edu 1777259Sgblack@eecs.umich.edubool 1787259Sgblack@eecs.umich.eduPersistentTable::isLocked(const Address& address) const 1797259Sgblack@eecs.umich.edu{ 1807259Sgblack@eecs.umich.edu assert(address == line_address(address)); 1817259Sgblack@eecs.umich.edu 1827259Sgblack@eecs.umich.edu // If an entry is present, it must be locked 1837259Sgblack@eecs.umich.edu return m_map_ptr->exist(address); 1847259Sgblack@eecs.umich.edu} 1857259Sgblack@eecs.umich.edu 1867259Sgblack@eecs.umich.eduint 1877351Sgblack@eecs.umich.eduPersistentTable::countStarvingForAddress(const Address& address) const 1887351Sgblack@eecs.umich.edu{ 1897351Sgblack@eecs.umich.edu if (m_map_ptr->exist(address)) { 1907351Sgblack@eecs.umich.edu PersistentTableEntry& entry = m_map_ptr->lookup(address); 1917351Sgblack@eecs.umich.edu return (entry.m_starving.count()); 1927351Sgblack@eecs.umich.edu } else { 1937259Sgblack@eecs.umich.edu return 0; 1947259Sgblack@eecs.umich.edu } 1957259Sgblack@eecs.umich.edu} 1967259Sgblack@eecs.umich.edu 1977259Sgblack@eecs.umich.eduint 1987259Sgblack@eecs.umich.eduPersistentTable::countReadStarvingForAddress(const Address& address) const 1997259Sgblack@eecs.umich.edu{ 2006735Sgblack@eecs.umich.edu if (m_map_ptr->exist(address)) { 2016261Sgblack@eecs.umich.edu PersistentTableEntry& entry = m_map_ptr->lookup(address); 2026261Sgblack@eecs.umich.edu return (entry.m_starving.count() - entry.m_request_to_write.count()); 2037259Sgblack@eecs.umich.edu } else { 2047259Sgblack@eecs.umich.edu return 0; 2057259Sgblack@eecs.umich.edu } 2066261Sgblack@eecs.umich.edu} 2077408Sgblack@eecs.umich.edu 2087259Sgblack@eecs.umich.eduvoid 2097351Sgblack@eecs.umich.eduPersistentTable::print(ostream& out) const 2107400SAli.Saidi@ARM.com{ 2117285Sgblack@eecs.umich.edu} 2127267Sgblack@eecs.umich.edu 2137287Sgblack@eecs.umich.edu