Index: branches/fault_tolerance/lib/generic_cache_tsar/include/generic_cache.h =================================================================== --- branches/fault_tolerance/lib/generic_cache_tsar/include/generic_cache.h (revision 724) +++ branches/fault_tolerance/lib/generic_cache_tsar/include/generic_cache.h (revision 724) @@ -0,0 +1,1033 @@ +/* -*- c++ -*- + * + * SOCLIB_LGPL_HEADER_BEGIN + * + * This file is part of SoCLib, GNU LGPLv2.1. + * + * SoCLib is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published + * by the Free Software Foundation; version 2.1 of the License. + * + * SoCLib is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with SoCLib; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + * + * SOCLIB_LGPL_HEADER_END + * + * Copyright (c) UPMC, Lip6 + * Alain Greiner July 2008 + * + * Maintainers: alain + */ + +//////////////////////////////////////////////////////////////////////////////// +// File : generic_cache.h +// Date : 07/01/2012 +// Authors : Alain Greiner +///////////////////////////////////////////////////////////////////////////////// +// This object is a generic, set associative, cache. +// Each slot can be in three states: VALID, EMPTY or ZOMBI. +// The ZOMBI state is used by cache coherence protocols to indicate +// a pending cleanup request. +// Hit if ( (matching tag) and (state == VALID). +// The replacement policy is pseudo-LRU. The victim selection process cannot +// fail if the ZOMBI state is not used. +// But it can fail if all ways are in ZOMBI state. +///////////////////////////////////////////////////////////////////////////////// +// Implementation note +// The DATA part is implemented as an uint32_t array[nways*nsets*nwords]. +// The DIRECTORY part is implemented as an uint32_t array[nways*nsets]. +// All methods requiring a dual port RAM or cache modification using +// an associative search have been deprecated. +///////////////////////////////////////////////////////////////////////////////// +// Constructor parameters are : +// - std::string &name +// - size_t nways : number of associativity levels +// - size_t nsets : number of sets +// - size_t nwords : number of words in a cache line +// The nways, nsets, nwords parameters must be power of 2 +// The nsets parameter cannot be larger than 1024 +// The nways parameter cannot be larger than 16 +// The nwords parameter cannot be larger than 64 +///////////////////////////////////////////////////////////////////////////////// +// Template parameter is : +// - addr_t : address format to access the cache +///////////////////////////////////////////////////////////////////////////////// + +#ifndef SOCLIB_GENERIC_CACHE_H +#define SOCLIB_GENERIC_CACHE_H + +#include +#include +#include "arithmetics.h" +#include "static_assert.h" +#include "mapping_table.h" +#include + +namespace soclib { + +enum cache_slot_state_e +{ + CACHE_SLOT_STATE_EMPTY, + CACHE_SLOT_STATE_VALID, + CACHE_SLOT_STATE_ZOMBI, +}; + +////////////////////////// +template +class GenericCache +////////////////////////// +{ + typedef uint32_t data_t; + typedef uint32_t be_t; + + data_t *r_data ; + addr_t *r_tag ; + int *r_state; + bool *r_lru ; + + size_t m_ways; + size_t m_sets; + size_t m_words; + + const soclib::common::AddressMaskingTable m_x ; + const soclib::common::AddressMaskingTable m_y ; + const soclib::common::AddressMaskingTable m_z ; + + ////////////////////////////////////////////////////////////// + inline data_t &cache_data(size_t way, size_t set, size_t word) + { + return r_data[(way*m_sets*m_words)+(set*m_words)+word]; + } + + ////////////////////////////////////////////// + inline addr_t &cache_tag(size_t way, size_t set) + { + return r_tag[(way*m_sets)+set]; + } + + ////////////////////////////////////////////// + inline bool &cache_lru(size_t way, size_t set) + { + return r_lru[(way*m_sets)+set]; + } + + ////////////////////////////////////////////// + inline int &cache_state(size_t way, size_t set) + { + return r_state[(way*m_sets)+set]; + } + + ///////////////////////////////////////////////// + inline void cache_set_lru(size_t way, size_t set) + { + size_t way2; + + cache_lru(way, set) = true; + + for (way2 = 0; way2 < m_ways; way2++ ) + { + if (cache_lru(way2, set) == false) return; + } + // all lines are new -> they all become old + for (way2 = 0; way2 < m_ways; way2++ ) + { + cache_lru(way2, set) = false; + } + } + + //////////////////////////////// + inline data_t be2mask( be_t be ) + { + data_t mask = 0; + if ( (be & 0x1) == 0x1 ) mask = mask | 0x000000FF; + if ( (be & 0x2) == 0x2 ) mask = mask | 0x0000FF00; + if ( (be & 0x4) == 0x4 ) mask = mask | 0x00FF0000; + if ( (be & 0x8) == 0x8 ) mask = mask | 0xFF000000; + return mask; + } + +public: + + ////////////////////////////////////////// + GenericCache( const std::string &name, + size_t nways, + size_t nsets, + size_t nwords) + : m_ways(nways), + m_sets(nsets), + m_words(nwords), + +#define l2 soclib::common::uint32_log2 + + m_x( l2(nwords), l2(sizeof(data_t))), + m_y( l2(nsets), l2(nwords) + l2(sizeof(data_t))), + m_z( 8*sizeof(addr_t) - l2(nsets) - l2(nwords) - l2(sizeof(data_t)), + l2(nsets) + l2(nwords) + l2(sizeof(data_t))) +#undef l2 + { + assert(IS_POW_OF_2(nways)); + assert(IS_POW_OF_2(nsets)); + assert(IS_POW_OF_2(nwords)); + assert(nwords); + assert(nsets); + assert(nways); + assert(nwords <= 64); + assert(nsets <= 1024); + assert(nways <= 16); + +#ifdef GENERIC_CACHE_DEBUG +std::cout << "constructing " << name << std::endl + << "- nways = " << nways << std::endl + << "- nsets = " << nsets << std::endl + << "- nwords = " << nwords << std::endl + << " m_x: " << m_x + << " m_y: " << m_y + << " m_z: " << m_z + << std::endl; +#endif + + r_data = new data_t[nways*nsets*nwords]; + r_tag = new addr_t[nways*nsets]; + r_state = new int[nways*nsets]; + r_lru = new bool[nways*nsets]; + } + + //////////////// + ~GenericCache() + { + delete [] r_data; + delete [] r_tag; + delete [] r_state; + delete [] r_lru; + } + + //////////////////// + inline void reset( ) + { + std::memset(r_data, 0, sizeof(*r_data)*m_ways*m_sets*m_words); + std::memset(r_tag, 0, sizeof(*r_tag)*m_ways*m_sets); + std::memset(r_state, CACHE_SLOT_STATE_EMPTY, sizeof(*r_state)*m_ways*m_sets); + std::memset(r_lru, 0, sizeof(*r_lru)*m_ways*m_sets); + } + + ///////////////////////////////////////////////////////////////////// + // Read a single 32 bits word. + // returns true if (matching tag) and (state == VALID) + // Both data & directory are accessed. + ///////////////////////////////////////////////////////////////////// + inline bool read( addr_t ad, + data_t* dt) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) + && (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + *dt = cache_data(way, set, word); + cache_set_lru(way, set); + return true; + } + } + return false; + } + + //////////////////////////////////////////////////////////////////// + // Read a single 32 bits word. + // returns true if (matching tag) and (state == VALID) + // Both data & directory are accessed. + // The selected way, set and word index are returned in case of hit. + ///////////////////////////////////////////////////////////////////// + inline bool read( addr_t ad, + data_t* dt, + size_t* selway, + size_t* selset, + size_t* selword) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + *selway = way; + *selset = set; + *selword = word; + *dt = cache_data(way, set, word); + cache_set_lru(way, set); + return true; + } + } + return false; + } + + //////////////////////////////////////////////////////////////////// + // Read a single 32 bits word when the ZOMBI state is used. + // Both data and directory are accessed. + // returns the access status in the state argument: + // - VALID : (matching tag) and (state == VALID) + // - ZOMBI : (matching tag) and (state == ZOMBI) + // - MISS : no matching tag or EMPTY state + // If VALID or ZOMBI, the data, the way, set and word index are + // returned in the other arguments. + //////////////////////////////////////////////////////////////////// + inline void read( addr_t ad, + data_t* dt, + size_t* selway, + size_t* selset, + size_t* selword, + int* state ) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + // default return values + *state = CACHE_SLOT_STATE_EMPTY; + *selway = 0; + *selset = 0; + *selword = 0; + *dt = 0; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( tag == cache_tag(way, set) ) // matching tag + { + + if ( cache_state(way, set) == CACHE_SLOT_STATE_VALID ) + { + *state = CACHE_SLOT_STATE_VALID; + *selway = way; + *selset = set; + *selword = word; + *dt = cache_data(way, set, word); + cache_set_lru(way, set); + } + else if ( cache_state(way, set) == CACHE_SLOT_STATE_ZOMBI ) + { + *state = CACHE_SLOT_STATE_ZOMBI; + *selway = way; + *selset = set; + *selword = word; + } + } + } + } + + //////////////////////////////////////////////////////////////////// + // Read a single 32 bits word, without LRU update. + // returns true if (matching tag) and (state == VALID) + // Both data & directory are accessed. + // The selected way, set and word index are returned in case of hit. + ///////////////////////////////////////////////////////////////////// + inline bool read_neutral( addr_t ad, + data_t* dt, + size_t* selway, + size_t* selset, + size_t* selword) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) + && (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + *selway = way; + *selset = set; + *selword = word; + *dt = cache_data(way, set, word); + return true; + } + } + return false; + } + + ///////////////////////////////////////////////////////////////////////////// + // Read one or two 32 bits word. + // Both data & directory are accessed. + // Hit if (matching tag) and (valid == true) and (zombi == false) + // If the addressed word is not the last in the cache line, + // two successive words are returned. + // The selected way, set and first word index are returned in case of hit. + // This function is used by the cc_vcache to get a 64 bits page table entry. + ///////////////////////////////////////////////////////////////////////////// + inline bool read( addr_t ad, + data_t* dt, + data_t* dt_next, + size_t* selway, + size_t* selset, + size_t* selword) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) + && (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + *dt = cache_data(way, set, word); + if ( word+1 < m_words) + { + *dt_next = cache_data(way, set, word+1); + } + *selway = way; + *selset = set; + *selword = word; + cache_set_lru(way, set); + return true; + } + } + return false; + } + + //////////////////////////////////////////////////////////////////// + // Read one or two 32 bits word. + // Both data and directory are accessed. + // returns the access status in the state argument: + // - VALID : (matching tag) and (state == VALID) + // - ZOMBI : (matching tag) and (state == ZOMBI) + // - MISS : no matching tag or EMPTY state + // If VALID or ZOMBI, the data, the way, set and word index are + // returned in the other arguments. + //////////////////////////////////////////////////////////////////// + inline void read( addr_t ad, + data_t* dt, + data_t* dt_next, + size_t* selway, + size_t* selset, + size_t* selword, + int* state ) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + // default return values + *state = CACHE_SLOT_STATE_EMPTY; + *selway = 0; + *selset = 0; + *selword = 0; + *dt = 0; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( tag == cache_tag(way, set) ) // matching tag + { + + if ( cache_state(way, set) == CACHE_SLOT_STATE_VALID ) + { + *state = CACHE_SLOT_STATE_VALID; + *selway = way; + *selset = set; + *selword = word; + *dt = cache_data(way, set, word); + if ( word+1 < m_words) + { + *dt_next = cache_data(way, set, word+1); + } else { + assert(false && "can't request 2 words at end of line"); + } + cache_set_lru(way, set); + } + else if ( cache_state(way, set) == CACHE_SLOT_STATE_ZOMBI ) + { + *state = CACHE_SLOT_STATE_ZOMBI; + *selway = way; + *selset = set; + *selword = word; + } + } + } + } + + /////////////////////////////////////////////////////////////////////////////// + // Checks the cache state for a given address. + // Only the directory is accessed. + // returns true if (matching tag) and (state == VALID) + // The selected way, set and first word index are returned in case of hit. + // This function can be used when we need to access the directory + // while we write in the data part with a different address in the same cycle. + /////////////////////////////////////////////////////////////////////////////// + inline bool hit( addr_t ad, + size_t* selway, + size_t* selset, + size_t* selword) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) + && (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + *selway = way; + *selset = set; + *selword = word; + cache_set_lru(way, set); + return true; + } + } + return false; + } + + /////////////////////////////////////////////////////////////////////////////// + // Checks the cache state for a given address, when the ZOMBI state is used. + // Only the directory is accessed. + // Returns the access status in the state argument: + // - VALID if (matching tag) and (state == VALID) + // - ZOMBI if (matching tag) and (state == ZOMBI) + // - EMPTY if no match or (state == EMPTY) + // The selected way, set and first word index are returned if not empty. + // This function can be used when we need to access the directory + // while we write in the data part with a different address in the same cycle. + /////////////////////////////////////////////////////////////////////////////// + inline void read_dir( addr_t ad, + int* state, + size_t* way, + size_t* set, + size_t* word) + { + const addr_t ad_tag = m_z[ad]; + const size_t ad_set = m_y[ad]; + const size_t ad_word = m_x[ad]; + + for ( size_t _way = 0; _way < m_ways; _way++ ) + { + if ( (ad_tag == cache_tag(_way, ad_set) ) and + (cache_state(_way, ad_set) != CACHE_SLOT_STATE_EMPTY) ) + { + *state = cache_state(_way, ad_set); + *way = _way; + *set = ad_set; + *word = ad_word; + return; + } + } + + // return value if not (VALID or ZOMBI) + *state = CACHE_SLOT_STATE_EMPTY; + } + + /////////////////////////////////////////////////////////////////////////////// + // Checks the cache state for a slot (set,way), when the ZOMBI state is used. + // Only the directory is accessed. + // Returns the access status and the tag value in the state and tag argument. + /////////////////////////////////////////////////////////////////////////////// + inline void read_dir( size_t way, + size_t set, + addr_t* tag, + int* state ) + { + *state = cache_state(way, set); + *tag = cache_tag(way, set); + } + + //////////////////////////////////////////// + inline addr_t get_tag(size_t way, size_t set) + { + return cache_tag(way, set); + } + + /////////////////////////////////////////////////////////////////// + // This function writes a complete 32 bits word + // It does not use the directory and cannot miss. + ////////////////////////////////////////////////////////////////// + inline void write(size_t way, + size_t set, + size_t word, + data_t data) + { + cache_data(way, set, word) = data; + cache_set_lru(way, set); + } + + //////////////////////////////////////////////////////////////////////////// + // this function writes up to 4 bytes, taking into account the byte enable. + // It does not use the directory and cannot miss. + //////////////////////////////////////////////////////////////////////////// + inline void write(size_t way, + size_t set, + size_t word, + data_t data, + be_t be) + { + data_t mask = be2mask(be); + data_t prev = cache_data(way, set, word); + cache_data(way, set, word) = (mask & data) | (~mask & prev); + cache_set_lru(way, set); + } + + ////////////////////////////////////////////////////////////////////////// + // This function invalidates a cache line identified by the set and way. + // It returns true if the line was valid, and returns the line index. + ////////////////////////////////////////////////////////////////////////// + inline bool inval(size_t way, + size_t set, + addr_t* nline) + { + if ( cache_state(way,set) == CACHE_SLOT_STATE_VALID ) + { + cache_state(way,set) = CACHE_SLOT_STATE_EMPTY; + *nline = (data_t)cache_tag(way,set)* m_sets + set; + return true; + } + return false; + } + + ////////////////////////////////////////////////////////////////////////////////// + // This function selects a victim slot in an associative set. + // It cannot fail, as a slot in ZOMBI state is considered EMPTY. + // - we search first an EMPTY slot + // - if no EMPTY slot, we search an OLD slot, using lru + // It returns the line index (Z + Y fields), the selected slot way and set, + // and a Boolean indicating that a cleanup is requested. + ////////////////////////////////////////////////////////////////////////////////// + inline bool victim_select(addr_t ad, + addr_t* victim, + size_t* way, + size_t* set) + { + bool found = false; + bool cleanup = false; + + *set = m_y[ad]; + *way = 0; + + // Search first empty slot + for ( size_t _way = 0 ; _way < m_ways && !found ; _way++ ) + { + if ( cache_state(_way, *set) != CACHE_SLOT_STATE_VALID ) // empty + { + found = true; + cleanup = false; + *way = _way; + } + } + + // If no empty slot, search first old slot (lru == false) + if ( !found ) + { + for ( size_t _way = 0 ; _way < m_ways && !found ; _way++ ) + { + if ( not cache_lru(_way, *set) ) + { + found = true; + cleanup = true; + *way = _way; + } + } + } + + assert(found && "all ways can't be new at the same time"); + *victim = (addr_t)((cache_tag(*way,*set) * m_sets) + *set); + return cleanup; + } + + ////////////////////////////////////////////////////////////////////////////////// + // This function selects a victim slot in an associative set. + // It can fail if all ways are in ZOMBI state. + // - we search first an EMPTY slot + // - if no empty slot, we search an OLD slot not in ZOMBI state, + // - if not found, we take the first not ZOMBI slot. + // It returns the line index (Z + Y fields), the selected slot way and set, + // and two Boolean indicating success and a required cleanup. + ////////////////////////////////////////////////////////////////////////////////// + inline void read_select(addr_t ad, + addr_t* victim, + size_t* way, + size_t* set, + bool* found, + bool* cleanup ) + { + size_t _set = m_y[ad]; + + *found = false; + + // Search first empty slot + for ( size_t _way = 0 ; _way < m_ways && !(*found) ; _way++ ) + { + if ( cache_state(_way, _set) == CACHE_SLOT_STATE_EMPTY ) + { + *found = true; + *cleanup = false; + *way = _way; + *set = m_y[ad]; + return; + } + } + // Search first not zombi old slot + for ( size_t _way = 0 ; _way < m_ways && !(*found) ; _way++ ) + { + if ( not cache_lru(_way, _set) and + (cache_state(_way, _set) != CACHE_SLOT_STATE_ZOMBI) ) + { + *found = true; + *cleanup = true; + *way = _way; + *set = m_y[ad]; + *victim = cache_tag(*way,_set) * m_sets + _set; + return; + } + } + // Search first not zombi slot + for ( size_t _way = 0 ; _way < m_ways && !(*found) ; _way++ ) + { + if ( cache_state(_way, _set) != CACHE_SLOT_STATE_ZOMBI) + { + *found = true; + *cleanup = true; + *way = _way; + *set = m_y[ad]; + *victim = cache_tag(*way,_set) * m_sets + _set; + return; + } + } + + // no slot found... + *found = false; + *cleanup = false; + } + + ////////////////////////////////////////////////////////////////// + // This function update the directory part of a slot + // identified by the way & set. + ////////////////////////////////////////////////////////////////// + inline void victim_update_tag( addr_t ad, + size_t way, + size_t set ) + { + addr_t tag = m_z[ad]; + + cache_tag(way, set) = tag; + cache_state(way, set) = CACHE_SLOT_STATE_VALID; + cache_set_lru(way, set); + } + + ////////////////////////////////////////////////////////////////// + // This function write the directory part of a slot + // identified by the way & set, when using the ZOMBI state. + ////////////////////////////////////////////////////////////////// + inline void write_dir( addr_t ad, + size_t way, + size_t set, + int state) + { + addr_t tag = m_z[ad]; + + assert( ( (state == CACHE_SLOT_STATE_VALID) or + (state == CACHE_SLOT_STATE_ZOMBI) or + (state == CACHE_SLOT_STATE_EMPTY) ) and + "illegal slot state argument in Generic Cache write_dir()"); + + assert( (way < m_ways) and + "too large way index argument in Generic Cache write_dir()"); + + assert( (set < m_sets) and + "too large set index argument in Generic Cache write_dir()"); + + cache_tag(way, set) = tag; + cache_state(way, set) = state; + + if ( state == CACHE_SLOT_STATE_VALID ) cache_set_lru(way, set); + } + + ////////////////////////////////////////////////////////////////// + // This function change the state of a slot + // identified by the way & set, when using the ZOMBI state. + // It does not affect the tag + ////////////////////////////////////////////////////////////////// + inline void write_dir( size_t way, + size_t set, + int state) + { + assert( ( (state == CACHE_SLOT_STATE_VALID) or + (state == CACHE_SLOT_STATE_ZOMBI) or + (state == CACHE_SLOT_STATE_EMPTY) ) and + "illegal slot state argument in Generic Cache write_dir()"); + + assert( (way < m_ways) and + "too large way index argument in Generic Cache write_dir()"); + + assert( (set < m_sets) and + "too large set index argument in Generic Cache write_dir()"); + + cache_state(way, set) = state; + + if ( state == CACHE_SLOT_STATE_VALID ) cache_set_lru(way, set); + } + + /////////////////////////////////////////////////////////////////// + // This function writes a full cache line in one single cycle. + // The target slot is identified by the way & set arguments. + // Both DATA and DIRECTORY are written + /////////////////////////////////////////////////////////////////// + inline void update(addr_t ad, + size_t way, + size_t set, + data_t* buf) + { + addr_t tag = m_z[ad]; + + cache_tag(way, set) = tag; + cache_state(way, set) = CACHE_SLOT_STATE_VALID; + cache_set_lru(way, set); + for ( size_t word = 0 ; word < m_words ; word++ ) + { + cache_data(way, set, word) = buf[word] ; + } + } + + /////////////////////////// + void fileTrace(FILE* file) + { + for( size_t nway = 0 ; nway < m_ways ; nway++) + { + for( size_t nset = 0 ; nset < m_sets ; nset++) + { + fprintf(file, "%d / ", (int)cache_state(nway, nset)); + fprintf(file, "way %d / ", (int)nway); + fprintf(file, "set %d / ", (int)nset); + fprintf(file, "@ = %08zX / ", + ((cache_tag(nway, nset)*m_sets+nset)*m_words*4)); + for( size_t nword = m_words ; nword > 0 ; nword--) + { + unsigned int data = cache_data(nway, nset, nword-1); + fprintf(file, "%08X ", data ); + } + fprintf(file, "\n"); + } + } + } + + //////////////////////// + inline void printTrace() + { + for ( size_t way = 0; way < m_ways ; way++ ) + { + for ( size_t set = 0 ; set < m_sets ; set++ ) + { + addr_t addr = (((addr_t)cache_tag(way,set))*m_words*m_sets+m_words*set)*4; + std::cout << std::dec << cache_state(way, set) + << " | way " << way + << " | set " << set + << std::hex << " | @ " << addr; + + for ( size_t word = 0 ; word < m_words ; word++ ) + { + std::cout << " | " << cache_data(way,set,word) ; + } + std::cout << std::endl ; + } + } + } + + /////////////////////////////////////////////////////////////////////////// + // This function is deprecated as it is difficult to implement in 1 cycle. + /////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool inval(addr_t ad) + { + bool hit = false; + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + + for ( size_t way = 0 ; way < m_ways && !hit ; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + hit = true; + cache_state(way, set) = CACHE_SLOT_STATE_EMPTY; + cache_lru(way, set) = false; + } + } + return hit; + } + + //////////////////////////////////////////////////////////////////////////////// + // This function is deprecated as it is difficult to implement in 1 cycle. + //////////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool inval( addr_t ad, + size_t* selway, + size_t* selset ) + { + bool hit = false; + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + + for ( size_t way = 0 ; way < m_ways && !hit ; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + hit = true; + cache_state(way, set) = CACHE_SLOT_STATE_EMPTY; + cache_lru(way, set) = false; + *selway = way; + *selset = set; + } + } + return hit; + } + + //////////////////////////////////////////////////////////////////////////////// + // This function is deprecated as the directory must be a dual port RAM... + //////////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool update( addr_t ad, + data_t* buf, + addr_t* victim ) + { + size_t set, way; + bool cleanup = victim_select(ad, victim, &way, &set); + victim_update_tag (ad, way, set); + + for ( size_t word = 0 ; word < m_words ; word++ ) { + cache_data(way, set, word) = buf[word] ; + } + + return cleanup; + } + + //////////////////////////////////////////////////////////////////////////// + // this function is deprecated, as it is difficult to implement in 1 cycle. + //////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool write(addr_t ad, + data_t dt) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + cache_data(way, set, word) = dt; + cache_set_lru(way, set); + return true; + } + } + return false; + } + + //////////////////////////////////////////////////////////////////////////// + // this function is deprecated, as it is difficult to implement in 1 cycle. + //////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool write(addr_t ad, + data_t dt, + be_t be) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + data_t mask = be2mask(be); + data_t prev = cache_data(way, set, word); + cache_data(way, set, word) = (mask & dt) | (~mask & prev); + cache_set_lru(way, set); + return true; + } + } + return false; + } + + ///////////////////////////////////////////////////////////////////////////// + // this function is deprecated, as it is difficult to implement in 1 cycle. + ///////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool write(addr_t ad, + data_t dt, + size_t* nway) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + cache_data(way, set, word) = dt; + cache_set_lru(way, set); + *nway = way; + return true; + } + } + return false; + } + + ///////////////////////////////////////////////////////////////////////////// + // this function is deprecated, as it is difficult to implement in 1 cycle. + ///////////////////////////////////////////////////////////////////////////// + __attribute__((deprecated)) + inline bool write(addr_t ad, + data_t dt, + size_t* nway, + be_t be) + { + const addr_t tag = m_z[ad]; + const size_t set = m_y[ad]; + const size_t word = m_x[ad]; + + for ( size_t way = 0; way < m_ways; way++ ) + { + if ( (tag == cache_tag(way, set)) and + (cache_state(way, set) == CACHE_SLOT_STATE_VALID) ) + { + data_t mask = be2mask(be); + data_t prev = cache_data(way, set, word); + cache_data(way, set, word) = (mask & dt) | (~mask & prev); + cache_set_lru(way, set); + *nway = way; + return true; + } + } + return false; + } + +}; + +} // namespace soclib + +#endif + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: + +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 + Index: branches/fault_tolerance/lib/generic_cache_tsar/metadata/generic_cache.sd =================================================================== --- branches/fault_tolerance/lib/generic_cache_tsar/metadata/generic_cache.sd (revision 724) +++ branches/fault_tolerance/lib/generic_cache_tsar/metadata/generic_cache.sd (revision 724) @@ -0,0 +1,15 @@ + +# -*- python -*- + +__version__ = "$Revision: 917 $" + +Module('caba:generic_cache_tsar', + classname = 'soclib::GenericCache', + header_files = ['../include/generic_cache.h',], + tmpl_parameters = [ + parameter.Type('addr_t'), + ], + uses = [Uses('common:mapping_table'), + Uses('common:address_masking_table', + data_t = parameter.Reference('addr_t')),], +) Index: branches/fault_tolerance/lib/generic_llsc_global_table/include/generic_llsc_global_table.h =================================================================== --- branches/fault_tolerance/lib/generic_llsc_global_table/include/generic_llsc_global_table.h (revision 724) +++ branches/fault_tolerance/lib/generic_llsc_global_table/include/generic_llsc_global_table.h (revision 724) @@ -0,0 +1,533 @@ +/* -*- c++ -*- + * + * SOCLIB_LGPL_HEADER_BEGIN + * + * This file is part of SoCLib, GNU LGPLv2.1. + * + * SoCLib is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published + * by the Free Software Foundation; version 2.1 of the License. + * + * SoCLib is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with SoCLib; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + * + * SOCLIB_LGPL_HEADER_END + * + * Alexandre JOANNOU + * + */ + +#ifndef SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H +#define SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H + +#include +#include +#include +#include +#include +#include + +#define RESERVATION_LIFE_SPAN 1 + +namespace soclib +{ + +////////////////////////// +//TODO switch to this +/* +template +< +size_t nb_slots, // max number of concerned shared resources +typename key_t, // key type => max number of key; TODO wich one ? +unsigned int t_network, // max number of cycle spent in the network when responding to a client (or more) +unsigned int t_inter_op, // min number of cycle between 2 reservation operation (or less but > 0) +typename addr_t // ressource identifier type +> +*/ +template +< +size_t nb_slots, // desired number of slots +unsigned int nb_procs, // number of processors in the system +unsigned int life_span, // registratioçn life span (in # of LL operations) +typename addr_t // address type +> +class GenericLLSCGlobalTable +//////////////////////////// +{ + private : + + const std::string name ; // component name + + uint32_t r_key [nb_slots] ; // array of key + addr_t r_addr [nb_slots] ; // array of addresses + bool r_val [nb_slots] ; // array of valid bits + + uint32_t r_next_key ; // value of the next key + uint64_t r_block_mask ; // mask for the slots blocks + uint64_t r_last_counter ; // mask for the slots blocks + size_t r_write_ptr ; // index of next slot to replace + size_t r_last_empty ; // index of last empty slot used + + mutable uint32_t m_cpt_evic ; // number of eviction in the table + mutable uint32_t m_cpt_ll ; // number of ll accesses to the table + mutable uint32_t m_cpt_ll_update ; // number of ll accesses to the table that trigger an update TODO check that + mutable uint32_t m_cpt_sc ; // number of sc accesses to the table + mutable uint32_t m_cpt_sc_success ; // number of sc accesses to the table that are successful + mutable uint32_t m_cpt_check ; // number of check accesses to the table + mutable uint32_t m_cpt_sw ; // number of sw accesses to the table + + //////////////////////////////////////////////////////////////////////////// + inline void upNextKey() + // This function generates a new value for the next key + { + // generating a new key in r_next_key + r_next_key++; + } + + //////////////////////////////////////////////////////////////////////////// + /* + inline void updateVictimSlot() + // This function selects the next slot to be evicted + // This is done by updating the value of r_write_ptr + { + // updates the position of the next slot to be replaced + + static unsigned int count = 0; + + + // for each slot, check if it actually is the slot to replace + // this is done by checking count % 2^(i+1) == (2^i)-1 + // 2^(i+1) being the period + // (2^i)-1 being the first apparition + // NB : the -1 in (2^i)-1 is here because of the 0 indexed array + + for (size_t i = 0 ; i < nb_slots; i++) + if (count % (int)pow(2,i+1) == pow(2,i)-1) + r_write_ptr = i; + + count = (count + 1) % (int) pow(2,nb_slots); // mustn't go further than 2^nb_slots + // or (2^nb_slots)+1 for a 1 indexed array + // 2^32 = periodicity of slot #31 + } + */ + //////////////////////////////////////////////////////////////////////////// + inline void updateVictimSlot() + // This function selects the next slot to be evicted + // This is done by updating the value of r_write_ptr + { + uint64_t new_counter; + uint64_t xor_counter; + + new_counter = newCounter(r_block_mask, r_last_counter); + xor_counter = new_counter ^ r_last_counter; + + for (size_t i = nb_slots - 1; i >= 0; --i) + { + if(xor_counter & (1 << i)) + { + r_write_ptr = i; + break; + } + } + + r_last_counter = new_counter; + } + + //////////////////////////////////////////////////////////////////////////// + inline uint64_t newCounter(const uint64_t& mask, + const uint64_t& counter) const + // This function generates the new counter //TODO comment more + { + return ((((~counter) & (counter << 1)) & mask) | (counter + 1)); + } + + //////////////////////////////////////////////////////////////////////////// + inline void init_block_mask() + //TODO + //This function selects the block mask to be used + //Need to provide another way to do that ? + { + /* + //try to dynamically compute the block mask ... + #define L2 soclib::common::uint32_log2 + unsigned int budget = nb_slots - (L2(nb_procs) + 1); //TODO +1? + #undef L2 + */ + + switch(nb_slots) + { + case 12: + r_block_mask = (uint64_t)0x000ULL; + break; + case 16 : + r_block_mask = (uint64_t)0xA800ULL; + break; + case 20 : + r_block_mask = (uint64_t)0xD5500ULL; + break; + case 24 : + r_block_mask = (uint64_t)0xDB5540ULL; + break; + case 28 : + r_block_mask = (uint64_t)0xEEDAAA0ULL; + break; + case 32 : + r_block_mask = (uint64_t)0xF776D550ULL; + break; + case 36 : + r_block_mask = (uint64_t)0xFBDDDB550ULL; + break; + case 40 : + r_block_mask = (uint64_t)0xFDF7BB6D50ULL; + break; + case 44 : + r_block_mask = (uint64_t)0xFEFBDEEDAA8ULL; + break; + case 48 : + r_block_mask = (uint64_t)0xFF7EFBDDDAA8ULL; + break; + case 52 : + r_block_mask = (uint64_t)0xFFBFBF7BBB6A8ULL; + break; + case 56 : + r_block_mask = (uint64_t)0xFFDFEFDF7BB6A8ULL; + break; + case 60 : + r_block_mask = (uint64_t)0xFFF7FDFDF7BB6A8ULL; + break; + case 64 : + r_block_mask = (uint64_t)0xFFFBFF7FBF7BB6A8ULL; + break; + default: + assert(false && "nb_slots must be either 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 or 64"); + } + } + + //////////////////////////////////////////////////////////////////////////// + inline int nextEmptySlot() const + // This function returns : + // - the position of the first next empty slot in the table + // (starting from the last empty slot used) + // and updates the r_last_empty_slot register + // - -1 if the table is full + { + uint64_t i; + for(i = 0; i < nb_slots; i++) + { + if (!r_val[i]) return i; + } + + return -1; + } + + //////////////////////////////////////////////////////////////////////////// + inline int hitAddr(const addr_t ad) const + // HIT on the address only + // This function takes an addr_t ad + // It returns : + // - the position of the first HIT in the table + // - -1 in case of MISS + // NB : HIT = (slot addr == ad) AND (slot is valid) + { + // checking all slots + for (size_t i = 0; i < nb_slots; i++) + { + // if HIT, returning its position + if(ad == r_addr[i] && r_val[i]) return i; + } + + // MISS + return -1; + } + + //////////////////////////////////////////////////////////////////////////// + inline int hitAddrKey(const addr_t ad, const uint32_t key) const + // HIT on the address AND the on the signature + // This function takes an addr_t ad and a uint32_t key + // It returns : + // - the position of the first HIT in the table + // - -1 in case of MISS + // NB : HIT = (slot addr == ad) AND (slot key == key) + // AND (slot is valid) + { + // checking all slots + for (size_t i = 0; i < nb_slots; i++) + { + // if HIT, returning its position + if(ad == r_addr[i] && key == r_key[i] && r_val[i]) return i; + } + + // MISS + return -1; + } + + //////////////////////////////////////////////////////////////////////////// + inline void reset() + { + // init the table + init(); + + // init stat counters + m_cpt_evic = 0; + m_cpt_ll = 0; + m_cpt_ll_update = 0; + m_cpt_sc = 0; + m_cpt_sc_success = 0; + m_cpt_check = 0; + m_cpt_sw = 0; + } + + + public: + + //////////////////////////////////////////////////////////////////////////// + GenericLLSCGlobalTable( const std::string &n = "llsc_global_table" ) + : name(n) + { + assert(nb_procs > 1); + init(); + init_block_mask(); + } + + //////////////////////////////////////////////////////////////////////////// + ~GenericLLSCGlobalTable() + { + } + + //////////////////////////////////////////////////////////////////////////// + // This function initializes the table (all slots empty) + inline void init() + { + // making all slots available by reseting all valid bits + std::memset(r_val, 0, sizeof(*r_val) * nb_slots); + std::memset(r_addr, 0, sizeof(*r_addr) * nb_slots); + std::memset(r_key, 0, sizeof(*r_key) * nb_slots); + + // init registers + r_next_key = 0; + r_last_counter = 0; //TODO static in updateVictimSlot() ? + r_write_ptr = 0; + r_last_empty = 0; + } + + //////////////////////////////////////////////////////////////////////////// + inline uint32_t ll(const addr_t ad) + // This method registers an LL in the table and returns the key associated + // with the registration + { + // increment the ll access counter (for stats) + m_cpt_ll++; + + // hit addr ? + // YES + // enough time left ? + // YES + // use this registration, return key + // NO + // update this registration with a new key, return new key + // NO + // table has an empty slot ? + // YES + // select empty slot + // NO + // select victim slot (r_write_ptr) + // update next victim + // open registration on selected slot + // update next key + // return the registration key + + // Is the address found in the table ? + int pos = hitAddr(ad); + + // Yes, then return the associated key + if (pos >= 0) + { +#if RESERVATION_LIFE_SPAN == 0 + return r_key[pos]; +#else + uint32_t absdiff = ( r_key[pos] > r_next_key) ? + r_key[pos] - r_next_key : + r_next_key - r_key[pos]; + + if(absdiff < life_span) return r_key[pos]; + + r_key[pos] = r_next_key; + upNextKey(); + m_cpt_ll_update++; + + return r_key[pos]; +#endif + } + + // No, then try to find an empty slot + pos = nextEmptySlot(); + + // If there is no empty slot, + // evict an existing registration + if (pos == -1) + { + // update the victim slot for the next eviction + updateVictimSlot(); + + // get the position of the evicted registration + pos = r_write_ptr; + + // increment the eviction counter (for stats) + m_cpt_evic++; + } + + // get the key for the new registration + uint32_t key = r_next_key; + // update the registration slot + r_key[pos] = key ; + r_addr[pos] = ad ; + r_val[pos] = true ; + // compute the next key + upNextKey(); + + // return the key of the new registration + return key; + + } + + //////////////////////////////////////////////////////////////////////////// + inline bool sc(const addr_t ad, const uint32_t key) + // This method checks if there is a valid registration for the SC (ad && + // key) and, in case of hit,invalidates the registration and returns true + // (returns false otherwise) + // + // The return value can be used to tell if the SC is atomic + { + // increment the sc access counter (for stats) + m_cpt_sc++; + // hit addr && hit key ? + // NO + // return miss + // YES + // inval registration and return hit + + // Is there a valid registration in the table ? + int pos = hitAddrKey(ad, key); + if(pos >= 0) + { + // increment the sc success counter (for stats) + m_cpt_sc_success++; + // invalidate the registration + r_val[pos] = false; + // return the success of the sc operation + return true; + } + else + { + // return the failure of the sc operation + return false; + } + } + + //////////////////////////////////////////////////////////////////////////// + inline bool check(const addr_t ad, const uint32_t key) const + // This method checks if there is a valid registration for the SC (ad && + // key) + // The return value can be used to tell if the SC is atomic + { + // increment the check access counter (for stats) + m_cpt_check++; + + return (hitAddrKey(ad, key) >= 0); + } + + //////////////////////////////////////////////////////////////////////////// + /* + inline void sw(const addr_t ad) + // This method checks if there is a valid registration for the given + // address and, in case of hit, invalidates the registration + { + // increment the sw access counter (for stats) + m_cpt_sw++; + // hit addr ? + // YES + // inval registration + // NO + // nothing + + // Is there a registration for the given address ? + int pos = hitAddr(ad); + // If there is one, invalidate it + if(pos >= 0) r_val[pos] = false; + } + */ + inline void sw(const addr_t ad_min, const addr_t ad_max) + // This method checks if there is / are valid registration(s) for the given + // range and, in case of hit(s), invalidates the registration(s) + { + // increment the sw access counter (for stats) + m_cpt_sw++; + // hit range ? + // YES + // inval registration(s) + // NO + // nothing + + // for every address in the given range ... + for (addr_t i = ad_min; i <= ad_max; i+=4) + { + // Is there a registration for the given address ? + int pos = hitAddr(i); + + // If there is one, invalidate it + if (pos >= 0) + { + r_val[pos] = false; + } + } + } + + //////////////////////////////////////////////////////////////////////////// + /* + void fileTrace(FILE* file) + { + } + */ + + //////////////////////////////////////////////////////////////////////////// + inline void print_trace(std::ostream& out = std::cout) + { + for ( size_t i = 0; i < nb_slots ; i++ ) + { + out << std::setw(3) << std::setfill(' ') << std::dec << i + << std::noshowbase + << " VLD_RX = " << r_val[i] + << std::uppercase + << " ADR_RX = 0x" << std::setw(8) << std::setfill('0') << std::hex << (r_addr[i] >> 2) + << " SGN_RX = 0x" << std::setw(8) << std::setfill('0') << std::hex << r_key[i] + << std::endl; + } + out << "NEXT_SGN_RX = 0x" << std::setw(8) << std::setfill('0') << std::hex << r_next_key << std::endl + << "CNT_RX = 0x" << std::setw(8) << std::setfill('0') << std::hex << r_last_counter << std::endl; + } + + //////////////////////////////////////////////////////////////////////////// + inline void print_stats(std::ostream& out = std::cout) + { + out << "# of ll accesses : " << m_cpt_ll << std::endl + << "# of ll updates : " << m_cpt_ll_update << std::endl + << "# of sc accesses : " << m_cpt_sc << std::endl + << "# of sc success : " << m_cpt_sc_success << std::endl + << "# of sw accesses : " << m_cpt_sw << std::endl + << "# of evictions : " << m_cpt_evic << std::endl ; + } + +}; + +} // end namespace soclib + +#endif + +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 Index: branches/fault_tolerance/lib/generic_llsc_global_table/metadata/generic_llsc_global_table.sd =================================================================== --- branches/fault_tolerance/lib/generic_llsc_global_table/metadata/generic_llsc_global_table.sd (revision 724) +++ branches/fault_tolerance/lib/generic_llsc_global_table/metadata/generic_llsc_global_table.sd (revision 724) @@ -0,0 +1,13 @@ +# -*- python -*- + +Module( + 'caba:generic_llsc_global_table', + classname = 'soclib::GenericLLSCGlobalTable', + header_files = ['../include/generic_llsc_global_table.h'], + tmpl_parameters = + [ + parameter.Int('nb_slots', min = 2, max = 64, default = 32), + parameter.Int('nb_procs', min = 2, max = 4096, default = 4095), # default should be 4096, but soclib-cc problem + parameter.Type('addr_t', default = 'sc_dt::sc_uint<40>') + ] +)