source: branches/ODCCP/lib/generic_cache_tsar/include/generic_cache.h @ 994

/* -*- 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 <alain.greiner@lip6.fr> 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 <systemc>
#include <cassert>
#include "arithmetics.h"
#include "static_assert.h"
#include "mapping_table.h"
#include <cstring>

namespace soclib { 

enum cache_slot_state_e
{
    CACHE_SLOT_STATE_EMPTY,
    CACHE_SLOT_STATE_VALID_CC,
    CACHE_SLOT_STATE_ZOMBI,
    CACHE_SLOT_STATE_VALID_NCC,
};

//////////////////////////
template<typename addr_t>
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<addr_t>  m_x ;
    const soclib::common::AddressMaskingTable<addr_t>  m_y ;
    const soclib::common::AddressMaskingTable<addr_t>  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);
    }

    inline int get_cache_state(int way, int set)
    {
        return cache_state(way,set);
    }
    
    /////////////////////////////////////////////////////////////////////
    // 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_CC) or (cache_state(way, set) == CACHE_SLOT_STATE_VALID_NCC)) )
            {
                *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_CC)or (cache_state(way, set) == CACHE_SLOT_STATE_VALID_NCC)))
            {
                *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_CC )
                {
                    *state   = CACHE_SLOT_STATE_VALID_CC;
                    *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_VALID_NCC )
                {
                    *state   = CACHE_SLOT_STATE_VALID_NCC;
                    *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_CC) or (cache_state(way, set) == CACHE_SLOT_STATE_VALID_NCC) ) )
            {
                *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_CC) ) ) 
            {
                *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_CC )
                {
                    *state   = CACHE_SLOT_STATE_VALID_CC;
                    *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);
                    }
                    cache_set_lru(way, set);
                }

                /*else if ( cache_state(way, set) == CACHE_SLOT_STATE_VALID_NCC )
                {
                    *state   = CACHE_SLOT_STATE_VALID_NCC;
                    *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);
                    }
                    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_CC)or(cache_state(way, set) == CACHE_SLOT_STATE_VALID_NCC) ) ) 
            {
                *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)
    {
       /**/ //std::cout << "write cache : way = "<<way<<" | set = "<<set<<" | word = "<<word<<" | data = "<<(uint32_t)data << std::endl;
        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_CC) )
        {
            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_CC ) )  // 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;
            }
        }
        //////////////////////////////////////////////////////////////
        /*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) and
                 (cache_state(_way, _set) == CACHE_SLOT_STATE_VALID_NCC) )
            {
                *found   = true;
                *cleanup = true;
                *way     = _way;
                *set     = m_y[ad];
                *victim  = (addr_t)((cache_tag(*way,_set) * m_sets) + _set);
                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_CC;
        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_CC) or
                  (state == CACHE_SLOT_STATE_VALID_NCC) 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_CC) or (state == CACHE_SLOT_STATE_VALID_NCC) ) 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_CC) or
                  (state == CACHE_SLOT_STATE_VALID_NCC) 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_CC) or (state == CACHE_SLOT_STATE_VALID_NCC) ) 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_CC;
        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_CC) ) 
            {
                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_CC) ) 
            {
                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_CC) ) 
            {
                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_CC) ) 
            {
                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_CC) ) 
            {
                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_CC) ) 
            {
                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