source: trunk/lib/generic_llsc_local_table/include/generic_llsc_local_table.h @ 360

/* -*- 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 <alexandre.joannou@lip6.fr>
 *
 */

#ifndef SOCLIB_GENERIC_LLSC_LOCAL_TABLE_H
#define SOCLIB_GENERIC_LLSC_LOCAL_TABLE_H

#include <systemc>
#include <cassert>
#include <cstring>
#include <iostream>
#include <iomanip>

namespace soclib {

//////////////////////////
//TODO switch to this
/*
template
<
size_t          nb_slots,   // max number of authorized atomic operation per agent
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
<
uint32_t    life_span               ,   // desired life-span for a reservation
size_t      nb_slots    = 1         ,   // desired number of reservation
typename    addr_t      = uint32_t  ,   // ressource identifier type
typename    index_t     = size_t    ,   // transaction index/identifier type (trdid size)
typename    key_t       = uint32_t      // key identifier type
>
class GenericLLSCLocalTable
///////////////////////////
{
    public:

    // command type
    enum cmd_t
    {
        LL_CMD  = 0x8,  // create a reservation in the table (to be called when an ll cmd is emited)
        LL_RSP  = 0x4,  // updates a reservation in the table (to be called when an ll rsp is received)
        SC_CMD  = 0x2,  // invalidate a reservation (if necessary) and reset the wait register
        SW_CMD  = 0x1,  // invalidate a reservation (if necessary)
        NOP     = 0x0   // no operation (internal updates only : aging counters)
    };

    struct in_t
    {
        addr_t  address ;   // the address  argument of the command
        index_t index   ;   // the index    argument of the command
        key_t   key     ;   // the key      argument of the command
        cmd_t   cmd     ;   // the command for the table to execute
    };

    struct out_t
    {
        bool    done    ;   // true if operation was actually performed
        bool    hit     ;   // true if there was a hit on the address
        key_t   key     ;   // the matching key for an SC_CMD
        index_t index   ;   // the index of the reservation for a LL_CMD
    };

    private :

    const std::string           name                ;   // component name

    addr_t                      r_addr  [nb_slots]  ;   // array of addresses
    key_t                       r_key   [nb_slots]  ;   // array of keys
    uint32_t                    r_cnt   [nb_slots]  ;   // array of aging counters
    bool                        r_val   [nb_slots]  ;   // array of valid bits

    uint32_t                    r_wait              ;   // number of cycles to wait (when trying to perform a reservation)
    uint32_t                    r_wait_cnt          ;   // counter counting down from r_wait to 0
    size_t                      r_write_ptr         ;   // index of next slot to replace
    size_t                      r_last_empty        ;   // index of last empty slot used

    uint32_t                    m_cpt_ll_cmd        ;   // number of ll_cmd accesses to the table
    uint32_t                    m_cpt_ll_cmd_done   ;   // number of ll_cmd accesses to the table (effectivelly done)
    uint32_t                    m_cpt_ll_rsp        ;   // number of ll_rsp accesses to the table
    uint32_t                    m_cpt_sc_cmd        ;   // number of sc_cmd accesses to the table
    uint32_t                    m_cpt_sw_cmd        ;   // number of sw_cmd accesses to the table
    uint32_t                    m_cpt_nop           ;   // number of nop    accesses to the table
    uint32_t                    m_cpt_evic          ;   // number of eviction in the table
    uint32_t                    m_cpt_death         ;   // number of death of reservations due to aging

    ////////////////////////////////////////////////////////////////////////////
    inline int hitAddr(const addr_t & address)
    //  HIT on the address only
    //  This function takes an addr_t address
    //  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(address == r_addr[i] && r_val[i]) return i;
        }

        // MISS
        return -1;
    }

    ////////////////////////////////////////////////////////////////////////////
    inline int nextEmptySlot()
    //  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
    {
        size_t i = r_last_empty;
        do
        {
            // checking if current slot is empty
            if(!r_val[i])
            {
                // updating last empty slot and returning its position
                r_last_empty = i;
                return i;
            }
            // selecting next slot
            i = (i+1) % nb_slots;
        }
        // stop if all slots have been tested
        while(i != r_last_empty);

        // the table is full
        return -1;
    }

    ////////////////////////////////////////////////////////////////////////////
    inline void updateVictimSlot()
    //  This function selects the next slot to be evicted
    //  This is done by updating the value of r_write_ptr
    {
        r_write_ptr = 0;
    }

    public:

    ////////////////////////////////////////////////////////////////////////////
    GenericLLSCLocalTable(  const std::string    &n = "llsc_local_table" )
    :   name(n)
    {
        init();
    }

    ////////////////////////////////////////////////////////////////////////////
    ~GenericLLSCLocalTable()
    {
    }

    ////////////////////////////////////////////////////////////////////////////
    inline void init()
    //  This function initializes the table (all slots empty)
    {
        // making all slots available by reseting all valid bits
        std::memset(r_val, 0, sizeof(*r_val)*nb_slots);

        // init registers
        r_wait              = 0;
        r_wait_cnt          = 0;
        r_write_ptr         = 0;
        r_last_empty        = 0;

        // init stat counters
        m_cpt_ll_cmd        = 0;
        m_cpt_ll_cmd_done   = 0;
        m_cpt_ll_rsp        = 0;
        m_cpt_sc_cmd        = 0;
        m_cpt_sw_cmd        = 0;
        m_cpt_nop           = 0;
        m_cpt_evic          = 0;
        m_cpt_death         = 0;
    }

    ////////////////////////////////////////////////////////////////////////////
    inline void exec(const in_t & in, out_t & out)
    // This function has to be called every cycle !
    // It implements the behaviour of the generic_llsc_local_table.
    // 5 commands can be performed :
    // - LL_CMD
    // - LL_RSP
    // - SC_CMD
    // - SW_CMD
    // - NOP
    // Each one of them are described further below
    {
        // First check the command
        switch(in.cmd)
        {
            case LL_CMD :
            // INPUTS :
            // - address
            //
            // Check if r_wait_cnt has reached 0
            // - YES
            //      - the wait counter is re initialized with the content of the
            //        r_wait register
            //      - the r_wait register is doubled (<< 1) (delay mechanism)
            //      - check if there is an empty slot
            //          if YES, select the empty slot
            //          if NO, select victim slot and update next victim
            //      - the address of the selected slot is initialized with the given
            //        address
            //      - the aging counter of the selected slot is initialized with
            //        the life-span of a reservation
            //      - the valid bit of the selected slot is set to true
            //
            //          - out.hit   <= don't care
            //          - out.done  <= true
            //          - out.key   <= don't care
            //          - out.index <= i the index of the selected slot
            //
            // - NO
            //      - decrement r_wait_cnt
            //
            //          - out.hit   <= don't care
            //          - out.done  <= false
            //          - out.key   <= don't care
            //          - out.index <= don't care
            {
                // increment the ll_cmd access counter (for stats)
                m_cpt_ll_cmd++;

                if(r_wait_cnt == 0)
                {
                    // increment the ll_cmd access counter (effectivelly done) (for stats)
                    m_cpt_ll_cmd_done++;

                    // increase the lenght of the next waiting session
                    //r_wait      = (r_wait << 1) + 1 ;
                    // re initialize the wait counter //TODO check this...
                    //r_wait_cnt  = r_wait;

                    // select a slot for the reservation
                    // first check for an empty slot ...
                    int pos = nextEmptySlot();
                    // If there is no empty slot,
                    // evict an existing registration
                    if (pos == -1)
                    {
                        // get the position of the evicted registration
                        pos = r_write_ptr;
                        // update the victim slot for the next eviction
                        updateVictimSlot();
                        // increment the eviction counter (for stats)
                        m_cpt_evic++;
                    }

                    // inscription in the slot
                    r_addr  [pos]   =   in.address  ;
                    r_cnt   [pos]   =   life_span   ;
                    r_val   [pos]   =   true        ;

                    // construct out argument
                    //out.hit   = don't care;
                    out.done    = 1;
                    //out.key   = don't care;
                    out.index   = pos;
                }
                else
                {
                    // decrement the wait counter
                    r_wait_cnt--;

                    // construct out argument
                    //out.hit   = don't care;
                    out.done    = 0;
                    //out.key   = don't care;
                    //out.index = don't care;
                }
            }
            break;
            case LL_RSP :
            // INPUTS :
            // - index
            // - key
            //
            //  - the key of the reservation is updated with the given key
            //
            //      - out.hit   <= don't care
            //      - out.done  <= true
            //      - out.key   <= don't care
            //      - out.index <= don't care
            {
                // increment the ll_rsp access counter (for stats)
                m_cpt_ll_rsp++;

                // insert new key in reservation
                r_key[in.index]  = in.key;

                // construct out argument
                out.hit     = 1;
                out.done    = 1;
                //out.key   = don't care;
                //out.index = don't care;
            }
            break;
            case SC_CMD :
            // INPUTS :
            // - address
            //
            // Check if there is a hit for the address
            // - HIT
            //      - invalidate reservation
            //      - reset r_wait to 0
            //
            //          - out.hit   <= true
            //          - out.done  <= true
            //          - out.key   <= r_key[hit_index]
            //          - out.index <= don't care
            //
            // - NO HIT
            //
            //      - out.hit   <= false
            //      - out.done  <= true
            //      - out.key   <= don't care
            //      - out.index <= don't care
            {
                // increment the sc_cmd access counter (for stats)
                m_cpt_sc_cmd++;

                // Is there a valid reservation in the table ?
                int pos = hitAddr(in.address);
                if(pos >= 0)
                {
                    // invalidate reservation
                    r_val[pos]  = false     ;
                    // reset r_wait to 0
                    r_wait      = 0         ;
                    // construct out argument
                    out.hit     = 1         ;
                    out.done    = 1         ;
                    out.key     = r_key[pos];
                }
                else
                {
                    // construct out argument
                    out.hit     = 0;
                    out.done    = 1;
                    //out.key   = don't care;
                    //out.index = don't care;
                }
            }
            break;
            case SW_CMD :
            // INPUTS :
            // - address
            //
            // Check if there is a hit for the address
            // - HIT
            //      - invalidate reservation
            //
            //          - out.hit   <= true
            //          - out.done  <= true
            //          - out.key   <= don't care
            //          - out.index <= don't care
            //
            // - NO HIT
            //
            //      - out.hit   <= false
            //      - out.done  <= true
            //      - out.key   <= don't care
            //      - out.index <= don't care
            {
                // increment the sw_cmd access counter (for stats)
                m_cpt_sw_cmd++;

                // Is there a valid reservation in the table ?
                int pos = hitAddr(in.address);
                if(pos >= 0)
                {
                    // invalidate reservation
                    r_val[pos]  = false     ;
                    // construct out argument
                    out.hit     = 1         ;
                    out.done    = 1         ;
                    //out.key   = don't care ;
                    //out.index = don't care;
                }
                else
                {
                    // construct out argument
                    out.hit     = 0;
                    out.done    = 1;
                    //out.key   = don't care;
                    //out.index = don't care;
                }
            }
            break;
            case NOP :
            // NOTHING except for the usual aging counter updates
            //
            //      - out.hit   <= don't care
            //      - out.done  <= 1
            //      - out.key   <= don't care
            //      - out.index <= don't care
            {
                // increment the nop access counter (for stats)
                m_cpt_nop++;
                // construct out argument
                //out.hit   = don't care;
                out.done    = 1;
                //out.key   = don't care;
                //out.index = don't care;
            }
            break;
        }
        // aging counters ...
        // for each slot
        for (size_t i = 0; i < nb_slots; i++)
        {
            // decrement the counter
            r_cnt[i]--;
            // check if the counter has reached 0 (for an actual reservation,
            // i.e. a valid reservation)
            if(r_cnt[i] == 0 && r_val[i])
            {
                // increment the death counter (for stats)
                m_cpt_death++;
                // invalidate the reservation
                r_val[i] = false;
            }
        }
    }

    ////////////////////////////////////////////////////////////////////////////
    inline void print_trace(std::ostream& out = std::cout)
    {
        out <<  " _________________________________________________" << std::endl
            <<  "| " << std::setw(47) << "generic_llsc_local_table" << " |" << std::endl
            <<  "| " << std::setw(47) << name << " |" << std::endl
            <<  " =================================================" << std::endl
            <<  "| "
            <<  std::setw(11) << "addr"   << " | "
            <<  std::setw(11) << "key"    << " | "
            <<  std::setw(11) << "cnt"    << " | "
            <<  std::setw(5)  << "val"
            << " |" << std::endl
            <<  " -------------------------------------------------" << std::endl;
        for ( size_t i = 0; i < nb_slots ; i++ )
        {
            out << "| "
                << std::showbase
                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
                << std::noshowbase
                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
                << std::setw(11) << std::setfill('0')   << std::dec       << r_cnt[i]     << " | "
                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
        }
        out <<  " -------------------------------------------------" << std::endl
            << std::noshowbase << std::dec << std::endl ;
    }

    ////////////////////////////////////////////////////////////////////////////
    inline void print_stats(std::ostream& out = std::cout)
    {
        out << "# of ll_cmd accesses                     : " << m_cpt_ll_cmd        << std::endl
            << "# of ll_cmd accesses (effectivelly done) : " << m_cpt_ll_cmd_done   << std::endl
            << "# of ll_rsp accesses                     : " << m_cpt_ll_rsp        << std::endl
            << "# of sc_cmd accesses                     : " << m_cpt_sc_cmd        << std::endl
            << "# of sw_cmd accesses                     : " << m_cpt_sw_cmd        << std::endl
            << "# of nop    accesses                     : " << m_cpt_nop           << std::endl
            << "# of eviction                            : " << m_cpt_evic          << std::endl
            << "# of death by aging                      : " << m_cpt_death         << std::endl ;
    }

};

} // namespace soclib

#endif

// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4