PersistentTable.cc revision 6791
110389SAndreas.Sandberg@ARM.com 210389SAndreas.Sandberg@ARM.com/* 310389SAndreas.Sandberg@ARM.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 410389SAndreas.Sandberg@ARM.com * All rights reserved. 510389SAndreas.Sandberg@ARM.com * 610389SAndreas.Sandberg@ARM.com * Redistribution and use in source and binary forms, with or without 710389SAndreas.Sandberg@ARM.com * modification, are permitted provided that the following conditions are 810389SAndreas.Sandberg@ARM.com * met: redistributions of source code must retain the above copyright 910389SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer; 1010389SAndreas.Sandberg@ARM.com * redistributions in binary form must reproduce the above copyright 1110389SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer in the 1210389SAndreas.Sandberg@ARM.com * documentation and/or other materials provided with the distribution; 1310389SAndreas.Sandberg@ARM.com * neither the name of the copyright holders nor the names of its 1410389SAndreas.Sandberg@ARM.com * contributors may be used to endorse or promote products derived from 1510389SAndreas.Sandberg@ARM.com * this software without specific prior written permission. 1610389SAndreas.Sandberg@ARM.com * 1710389SAndreas.Sandberg@ARM.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1810389SAndreas.Sandberg@ARM.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1910389SAndreas.Sandberg@ARM.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2010389SAndreas.Sandberg@ARM.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2110389SAndreas.Sandberg@ARM.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2210389SAndreas.Sandberg@ARM.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2310389SAndreas.Sandberg@ARM.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2410389SAndreas.Sandberg@ARM.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2510389SAndreas.Sandberg@ARM.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2610389SAndreas.Sandberg@ARM.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2710389SAndreas.Sandberg@ARM.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2810389SAndreas.Sandberg@ARM.com */ 2910389SAndreas.Sandberg@ARM.com 3010389SAndreas.Sandberg@ARM.com#include "PersistentTable.hh" 3110389SAndreas.Sandberg@ARM.com#include "NetDest.h" 3210389SAndreas.Sandberg@ARM.com#include "Map.h" 3310389SAndreas.Sandberg@ARM.com#include "Address.h" 3410389SAndreas.Sandberg@ARM.com#include "AbstractChip.h" 3510389SAndreas.Sandberg@ARM.com#include "util.h" 3610389SAndreas.Sandberg@ARM.com 3710389SAndreas.Sandberg@ARM.com// randomize so that handoffs are not locality-aware 3810389SAndreas.Sandberg@ARM.com// int persistent_randomize[] = {0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15}; 3910389SAndreas.Sandberg@ARM.com// int persistent_randomize[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 4011793Sbrandon.potter@amd.com 4111793Sbrandon.potter@amd.com 4210389SAndreas.Sandberg@ARM.comclass PersistentTableEntry { 4310389SAndreas.Sandberg@ARM.compublic: 4410389SAndreas.Sandberg@ARM.com NetDest m_starving; 4510389SAndreas.Sandberg@ARM.com NetDest m_marked; 4610389SAndreas.Sandberg@ARM.com NetDest m_request_to_write; 4710389SAndreas.Sandberg@ARM.com}; 4810389SAndreas.Sandberg@ARM.com 4910389SAndreas.Sandberg@ARM.comPersistentTable::PersistentTable(AbstractChip* chip_ptr, int version) 5012237Sandreas.sandberg@arm.com{ 5110389SAndreas.Sandberg@ARM.com m_chip_ptr = chip_ptr; 5210389SAndreas.Sandberg@ARM.com m_map_ptr = new Map<Address, PersistentTableEntry>; 5310389SAndreas.Sandberg@ARM.com m_version = version; 5410389SAndreas.Sandberg@ARM.com} 5510389SAndreas.Sandberg@ARM.com 5610389SAndreas.Sandberg@ARM.comPersistentTable::~PersistentTable() 5710389SAndreas.Sandberg@ARM.com{ 5812237Sandreas.sandberg@arm.com delete m_map_ptr; 5910389SAndreas.Sandberg@ARM.com m_map_ptr = NULL; 6010389SAndreas.Sandberg@ARM.com m_chip_ptr = NULL; 6110389SAndreas.Sandberg@ARM.com} 6210389SAndreas.Sandberg@ARM.com 6310389SAndreas.Sandberg@ARM.comvoid PersistentTable::persistentRequestLock(const Address& address, MachineID locker, AccessType type) 6410389SAndreas.Sandberg@ARM.com{ 6510389SAndreas.Sandberg@ARM.com 6610389SAndreas.Sandberg@ARM.com // if (locker == m_chip_ptr->getID() ) 6710389SAndreas.Sandberg@ARM.com // cout << "Chip " << m_chip_ptr->getID() << ": " << llocker << " requesting lock for " << address << endl; 6810389SAndreas.Sandberg@ARM.com 6910389SAndreas.Sandberg@ARM.com // MachineID locker = (MachineID) persistent_randomize[llocker]; 7010389SAndreas.Sandberg@ARM.com 7110389SAndreas.Sandberg@ARM.com assert(address == line_address(address)); 7210389SAndreas.Sandberg@ARM.com if (!m_map_ptr->exist(address)) { 7310389SAndreas.Sandberg@ARM.com // Allocate if not present 7410389SAndreas.Sandberg@ARM.com PersistentTableEntry entry; 7510389SAndreas.Sandberg@ARM.com entry.m_starving.add(locker); 7610389SAndreas.Sandberg@ARM.com if (type == AccessType_Write) { 7710389SAndreas.Sandberg@ARM.com entry.m_request_to_write.add(locker); 7810389SAndreas.Sandberg@ARM.com } 7910389SAndreas.Sandberg@ARM.com m_map_ptr->add(address, entry); 8010389SAndreas.Sandberg@ARM.com } else { 8110389SAndreas.Sandberg@ARM.com PersistentTableEntry& entry = m_map_ptr->lookup(address); 8210389SAndreas.Sandberg@ARM.com assert(!(entry.m_starving.isElement(locker))); // Make sure we're not already in the locked set 8310389SAndreas.Sandberg@ARM.com 8412237Sandreas.sandberg@arm.com entry.m_starving.add(locker); 8510389SAndreas.Sandberg@ARM.com if (type == AccessType_Write) { 8610389SAndreas.Sandberg@ARM.com entry.m_request_to_write.add(locker); 8712237Sandreas.sandberg@arm.com } 8812237Sandreas.sandberg@arm.com assert(entry.m_marked.isSubset(entry.m_starving)); 8910389SAndreas.Sandberg@ARM.com } 9010389SAndreas.Sandberg@ARM.com} 9110389SAndreas.Sandberg@ARM.com 9210389SAndreas.Sandberg@ARM.comvoid PersistentTable::persistentRequestUnlock(const Address& address, MachineID unlocker) 9310389SAndreas.Sandberg@ARM.com{ 9410389SAndreas.Sandberg@ARM.com // if (unlocker == m_chip_ptr->getID() ) 9510389SAndreas.Sandberg@ARM.com // cout << "Chip " << m_chip_ptr->getID() << ": " << uunlocker << " requesting unlock for " << address << endl; 9610389SAndreas.Sandberg@ARM.com 9710389SAndreas.Sandberg@ARM.com // MachineID unlocker = (MachineID) persistent_randomize[uunlocker]; 9810389SAndreas.Sandberg@ARM.com 9910389SAndreas.Sandberg@ARM.com assert(address == line_address(address)); 10010389SAndreas.Sandberg@ARM.com assert(m_map_ptr->exist(address)); 10110389SAndreas.Sandberg@ARM.com PersistentTableEntry& entry = m_map_ptr->lookup(address); 10210389SAndreas.Sandberg@ARM.com assert(entry.m_starving.isElement(unlocker)); // Make sure we're in the locked set 10310389SAndreas.Sandberg@ARM.com assert(entry.m_marked.isSubset(entry.m_starving)); 10410389SAndreas.Sandberg@ARM.com entry.m_starving.remove(unlocker); 10510389SAndreas.Sandberg@ARM.com entry.m_marked.remove(unlocker); 10610389SAndreas.Sandberg@ARM.com entry.m_request_to_write.remove(unlocker); 10710389SAndreas.Sandberg@ARM.com assert(entry.m_marked.isSubset(entry.m_starving)); 10810389SAndreas.Sandberg@ARM.com 10910389SAndreas.Sandberg@ARM.com // Deallocate if empty 11010389SAndreas.Sandberg@ARM.com if (entry.m_starving.isEmpty()) { 11112237Sandreas.sandberg@arm.com assert(entry.m_marked.isEmpty()); 11210389SAndreas.Sandberg@ARM.com m_map_ptr->erase(address); 11310389SAndreas.Sandberg@ARM.com } 11410389SAndreas.Sandberg@ARM.com} 11510389SAndreas.Sandberg@ARM.com 11610389SAndreas.Sandberg@ARM.combool PersistentTable::okToIssueStarving(const Address& address) const 11710389SAndreas.Sandberg@ARM.com{ 11810389SAndreas.Sandberg@ARM.com assert(address == line_address(address)); 11910389SAndreas.Sandberg@ARM.com if (!m_map_ptr->exist(address)) { 12010389SAndreas.Sandberg@ARM.com return true; // No entry present 12110389SAndreas.Sandberg@ARM.com } else if (m_map_ptr->lookup(address).m_starving.isElement( (MachineID) {MachineType_L1Cache, m_version})) { 12210389SAndreas.Sandberg@ARM.com return false; // We can't issue another lockdown until are previous unlock has occurred 123 } else { 124 return (m_map_ptr->lookup(address).m_marked.isEmpty()); 125 } 126} 127 128MachineID PersistentTable::findSmallest(const Address& address) const 129{ 130 assert(address == line_address(address)); 131 assert(m_map_ptr->exist(address)); 132 const PersistentTableEntry& entry = m_map_ptr->lookup(address); 133 // cout << "Node " << m_chip_ptr->getID() << " returning " << persistent_randomize[entry.m_starving.smallestElement()] << " for findSmallest(" << address << ")" << endl; 134 // return (MachineID) persistent_randomize[entry.m_starving.smallestElement()]; 135 return (MachineID) { MachineType_L1Cache, entry.m_starving.smallestElement() }; 136} 137 138AccessType PersistentTable::typeOfSmallest(const Address& address) const 139{ 140 assert(address == line_address(address)); 141 assert(m_map_ptr->exist(address)); 142 const PersistentTableEntry& entry = m_map_ptr->lookup(address); 143 if (entry.m_request_to_write.isElement((MachineID) {MachineType_L1Cache, entry.m_starving.smallestElement()})) { 144 return AccessType_Write; 145 } else { 146 return AccessType_Read; 147 } 148} 149 150void PersistentTable::markEntries(const Address& address) 151{ 152 assert(address == line_address(address)); 153 if (m_map_ptr->exist(address)) { 154 PersistentTableEntry& entry = m_map_ptr->lookup(address); 155 assert(entry.m_marked.isEmpty()); // None should be marked 156 entry.m_marked = entry.m_starving; // Mark all the nodes currently in the table 157 } 158} 159 160bool PersistentTable::isLocked(const Address& address) const 161{ 162 assert(address == line_address(address)); 163 // If an entry is present, it must be locked 164 return (m_map_ptr->exist(address)); 165} 166 167int PersistentTable::countStarvingForAddress(const Address& address) const 168{ 169 if (m_map_ptr->exist(address)) { 170 PersistentTableEntry& entry = m_map_ptr->lookup(address); 171 return (entry.m_starving.count()); 172 } 173 else { 174 return 0; 175 } 176} 177 178int PersistentTable::countReadStarvingForAddress(const Address& address) const 179{ 180 int count = 0; 181 if (m_map_ptr->exist(address)) { 182 PersistentTableEntry& entry = m_map_ptr->lookup(address); 183 return (entry.m_starving.count() - entry.m_request_to_write.count()); 184 } 185 else { 186 return 0; 187 } 188} 189 190 191