source: trunk/lib/generic_llsc_global_table/include/generic_llsc_global_table.h @ 524

Last change on this file since 524 was 524, checked in by cfuguet, 11 years ago

The last commit to solve the bug in the SW access
to the LLSC table was imcomplete.

In the SW method the increment of the address to
check the [min, max] interval must be 4 (cell_size),
as the addresses stored in the table are byte
addresses.

File size: 17.9 KB
RevLine 
[291]1/* -*- c++ -*-
2 *
3 * SOCLIB_LGPL_HEADER_BEGIN
4 *
5 * This file is part of SoCLib, GNU LGPLv2.1.
6 *
7 * SoCLib is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU Lesser General Public License as published
9 * by the Free Software Foundation; version 2.1 of the License.
10 *
11 * SoCLib is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with SoCLib; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 * 02110-1301 USA
20 *
21 * SOCLIB_LGPL_HEADER_END
22 *
23 * Alexandre JOANNOU <alexandre.joannou@lip6.fr>
24 *
25 */
26
27#ifndef SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H
28#define SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H
29
30#include <systemc>
31#include <arithmetics.h>
32#include <cassert>
33#include <cstring>
34#include <cmath>
35#include <iostream>
36#include <iomanip>
37
38namespace soclib
39{
40
41//////////////////////////
42//TODO switch to this
43/*
44template
45<
46size_t          nb_slots,   // max number of concerned shared resources
47typename        key_t,      // key type => max number of key; TODO wich one ?
48unsigned int    t_network,  // max number of cycle spent in the network when responding to a client (or more)
49unsigned int    t_inter_op, // min number of cycle between 2 reservation operation (or less but > 0)
50typename        addr_t      // ressource identifier type
51>
52*/
53template
54<
55size_t          nb_slots,   // desired number of slots
56unsigned int    nb_procs,   // number of processors in the system
57unsigned int    life_span,  // registratioçn life span (in # of LL operations)
58typename        addr_t      // address type
59>
60class GenericLLSCGlobalTable
61////////////////////////////
62{
63    private :
64
65    const std::string           name              ; // component name
66
67    uint32_t                    r_key  [nb_slots] ; // array of key
68    addr_t                      r_addr [nb_slots] ; // array of addresses
69    bool                        r_val  [nb_slots] ; // array of valid bits
70
71    uint32_t                    r_next_key        ; // value of the next key
72    sc_dt::sc_uint<nb_slots>    r_block_mask      ; // mask for the slots blocks
73    sc_dt::sc_uint<nb_slots>    r_last_counter    ; // mask for the slots blocks
74    size_t                      r_write_ptr       ; // index of next slot to replace
75    size_t                      r_last_empty      ; // index of last empty slot used
76
77    uint32_t                    m_cpt_evic        ; // number of eviction in the table
78    uint32_t                    m_cpt_ll          ; // number of ll accesses to the table
79    uint32_t                    m_cpt_ll_update   ; // number of ll accesses to the table that trigger an update TODO check that
80    uint32_t                    m_cpt_sc          ; // number of sc accesses to the table
81    uint32_t                    m_cpt_sc_success  ; // number of sc accesses to the table that are successful
82    uint32_t                    m_cpt_sw          ; // number of sw accesses to the table
83
84    ////////////////////////////////////////////////////////////////////////////
85    inline void upNextKey()
86    //  This function generates a new value for the next key
87    {
88        // generating a new key in r_next_key
89        r_next_key++;
90    }
91
92    ////////////////////////////////////////////////////////////////////////////
93    /*
94    inline void updateVictimSlot()
95    //  This function selects the next slot to be evicted
96    //  This is done by updating the value of r_write_ptr
97    {
98        // updates the position of the next slot to be replaced
99
100        static unsigned int count = 0;
101
102
103        // for each slot, check if it actually is the slot to replace
104        // this is done by checking count % 2^(i+1) == (2^i)-1
105        // 2^(i+1) being the period
106        // (2^i)-1 being the first apparition
107        // NB : the -1 in (2^i)-1 is here because of the 0 indexed array
108
109        for (size_t i = 0 ; i < nb_slots; i++)
110            if (count % (int)pow(2,i+1) == pow(2,i)-1)
111                r_write_ptr = i;
112
113        count = (count + 1) % (int) pow(2,nb_slots);    // mustn't go further than 2^nb_slots
114                                                        // or (2^nb_slots)+1 for a 1 indexed array
115                                                        // 2^32 = periodicity of slot #31
116    }
117    */
118    ////////////////////////////////////////////////////////////////////////////
119    inline void updateVictimSlot()
120    //  This function selects the next slot to be evicted
121    //  This is done by updating the value of r_write_ptr
122    {
123        sc_dt::sc_uint<nb_slots> new_counter;
124        sc_dt::sc_uint<nb_slots> xor_counter;
125
126        new_counter = newCounter(r_block_mask, r_last_counter);
127        xor_counter = new_counter ^ r_last_counter;
128
129        for (size_t i = nb_slots - 1; i >= 0; --i)
130        {
131            if(xor_counter[i])
132            {
133                r_write_ptr = i;
134                break;
135            }
136        }
137
138        r_last_counter = new_counter;
139    }
140
141    ////////////////////////////////////////////////////////////////////////////
142    inline sc_dt::sc_uint<nb_slots> newCounter(const sc_dt::sc_uint<nb_slots>& mask,
143                                               const sc_dt::sc_uint<nb_slots>& counter)
144    // This function generates the new counter //TODO comment more
145    {
146        //
147        return ((((~counter) & (counter << 1)) & mask) | (counter + 1));
148    }
149
150    ////////////////////////////////////////////////////////////////////////////
151    inline void init_block_mask()
152    //TODO
153    //This function selects the block mask to be used
154    //Need to provide another way to do that ?
155    {
156        /*
157        //try to dynamically compute the block mask ...
158        #define L2 soclib::common::uint32_log2
159        unsigned int budget = nb_slots - (L2(nb_procs) + 1); //TODO +1?
160        #undef L2
161        */
162
163        switch(nb_slots)
164        {
165            case 12:
166            r_block_mask = sc_dt::sc_uint<nb_slots>("0x000");
167            break;
168            case 16 :
169            r_block_mask = sc_dt::sc_uint<nb_slots>("0xA800");
170            break;
171            case 20 :
172            r_block_mask = sc_dt::sc_uint<nb_slots>("0xD5500");
173            break;
174            case 24 :
175            r_block_mask = sc_dt::sc_uint<nb_slots>("0xDB5540");
176            break;
177            case 28 :
178            r_block_mask = sc_dt::sc_uint<nb_slots>("0xEEDAAA0");
179            break;
180            case 32 :
181            r_block_mask = sc_dt::sc_uint<nb_slots>("0xF776D550");
182            break;
183            case 36 :
184            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFBDDDB550");
185            break;
186            case 40 :
187            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFDF7BB6D50");
188            break;
189            case 44 :
190            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFEFBDEEDAA8");
191            break;
192            case 48 :
193            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFF7EFBDDDAA8");
194            break;
195            case 52 :
196            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFBFBF7BBB6A8");
197            break;
198            case 56 :
199            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFDFEFDF7BB6A8");
200            break;
201            case 60 :
202            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFF7FDFDF7BB6A8");
203            break;
204            case 64 :
205            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFFBFF7FBF7BB6A8");
206            break;
207            default:
208            assert(false && "nb_slots must be either 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 or 64");
209        }
210    }
211
212    ////////////////////////////////////////////////////////////////////////////
213    inline int nextEmptySlot()
214    //  This function returns :
215    //  - the position of the first next empty slot in the table
216    //    (starting from the last empty slot used)
217    //    and updates the r_last_empty_slot register
218    //  - -1 if the table is full
219    {
220        size_t i = r_last_empty;
221        do
222        {
223            // checking if current slot is empty
224            if(!r_val[i])
225            {
226                // updating last empty slot and returning its position
227                r_last_empty = i;
228                return i;
229            }
230            // selecting next slot
231            i = (i+1) % nb_slots;
232        }
233        // stop if all slots have been tested
234        while(i != r_last_empty);
235
236        // the table is full
237        return -1;
238    }
239
240    ////////////////////////////////////////////////////////////////////////////
241    inline int hitAddr(const addr_t ad)
242    //  HIT on the address only
243    //  This function takes an addr_t ad
244    //  It returns :
245    //  - the position of the first HIT in the table
246    //  - -1 in case of MISS
247    //  NB : HIT = (slot addr == ad) AND (slot is valid)
248    {
249        // checking all slots
250        for (size_t i = 0; i < nb_slots; i++)
251        {
252            // if HIT, returning its position
253            if(ad == r_addr[i] && r_val[i]) return i;
254        }
255
256        // MISS
257        return -1;
258    }
259
260    ////////////////////////////////////////////////////////////////////////////
261    inline int hitAddrKey(const addr_t ad, const uint32_t key)
262    //  HIT on the address AND the on the signature
263    //  This function takes an addr_t ad and a uint32_t key
264    //  It returns :
265    //  - the position of the first HIT in the table
266    //  - -1 in case of MISS
267    //  NB : HIT = (slot addr == ad) AND (slot key == key)
268    //                               AND (slot is valid)
269    {
270        // checking all slots
271        for (size_t i = 0; i < nb_slots; i++)
272        {
273            // if HIT, returning its position
274            if(ad == r_addr[i] && key == r_key[i] && r_val[i]) return i;
275        }
276
277        // MISS
278        return -1;
279    }
280
[334]281    ////////////////////////////////////////////////////////////////////////////
282    inline void reset()
283    {
284        // init the table
285        init();
286
287        // init stat counters
288        m_cpt_evic          = 0;
289        m_cpt_ll            = 0;
290        m_cpt_ll_update     = 0;
291        m_cpt_sc            = 0;
292        m_cpt_sc_success    = 0;
293        m_cpt_sw            = 0;
294    }
295
296
[291]297    public:
298
299    ////////////////////////////////////////////////////////////////////////////
300    GenericLLSCGlobalTable( const std::string   &n = "llsc_global_table" )
301    :   name(n)
302    {
303        #define L2 soclib::common::uint32_log2
[382]304        assert(nb_procs > 1); 
305        assert((int)nb_slots >= L2(nb_procs));
[291]306        #undef L2
307        init();
308        init_block_mask();
309    }
310
311    ////////////////////////////////////////////////////////////////////////////
312    ~GenericLLSCGlobalTable()
313    {
314    }
315
316    ////////////////////////////////////////////////////////////////////////////
[334]317    //  This function initializes the table (all slots empty)
[291]318    inline void init()
319    {
320        // making all slots available by reseting all valid bits
[514]321        std::memset(r_val,  0, sizeof(*r_val) * nb_slots);
322        std::memset(r_addr, 0, sizeof(*r_addr) * nb_slots);
323        std::memset(r_key,  0, sizeof(*r_key) * nb_slots);
[291]324
325        // init registers
326        r_next_key          = 0;
327        r_last_counter      = 0; //TODO static in updateVictimSlot() ?
328        r_write_ptr         = 0;
329        r_last_empty        = 0;
330    }
331
332    ////////////////////////////////////////////////////////////////////////////
333    inline uint32_t ll(const addr_t ad)
334    //  This method registers an LL in the table and returns the key associated
335    //  with the registration
336    {
337        // increment the ll access counter (for stats)
338        m_cpt_ll++;
339
340        // hit addr ?
341        // YES
342        //      enough time left ?
343        //      YES
344        //          use this registration, return key
345        //      NO
346        //          update this registration with a new key, return new key
347        // NO
348        //      table has an empty slot ?
349        //      YES
350        //              select empty slot
351        //      NO
352        //              select victim slot (r_write_ptr)
353        //              update next victim
354        //      open registration on selected slot
355        //      update next key
356        //      return the registration key
357
358        //  Is the address found in the table ?
359        int pos = hitAddr(ad);
360
361        //  Yes, then return the associated key
362        if (pos >= 0)
363        {
364            if(r_key[pos] - r_next_key > life_span)
365                return r_key[pos];
366            r_key[pos] = r_next_key;
367            upNextKey();
368            m_cpt_ll_update++;
369            return r_key[pos];
370        }
371
372        //  No, then try to find an empty slot
373        pos = nextEmptySlot();
374
375        //  If there is no empty slot,
376        //  evict an existing registration
377        if (pos == -1)
378        {
379            //  get the position of the evicted registration
380            pos = r_write_ptr;
381            //  update the victim slot for the next eviction
382            updateVictimSlot();
383            // increment the eviction counter (for stats)
384            m_cpt_evic++;
385        }
386
387        // get the key for the new registration
388        uint32_t key    = r_next_key;
389        //  update the registration slot
390        r_key[pos]      = key   ;
391        r_addr[pos]     = ad    ;
392        r_val[pos]      = true  ;
393        //  compute the next key
394        upNextKey();
395
396        // return the key of the new registration
397        return key;
398
399    }
400
401    ////////////////////////////////////////////////////////////////////////////
402    inline bool sc(const addr_t ad, const uint32_t key)
403    //  This method checks if there is a valid registration for the SC (ad &&
404    //  key) and, in case of hit,invalidates the registration and returns true
405    //  (returns false otherwise)
406    //
407    //  The return value can be used to tell if the SC is atomic
408    {
409        // increment the sc access counter (for stats)
410        m_cpt_sc++;
411        // hit addr && hit key ?
412        // NO
413        //      return miss
414        // YES
415        //      inval registration and return hit
416
417        //  Is there a valid registration in the table ?
418        int pos = hitAddrKey(ad, key);
419        if(pos >= 0)
420        {
421            // increment the sc success counter (for stats)
422            m_cpt_sc_success++;
423            // invalidate the registration
424            r_val[pos] = false;
425            // return the success of the sc operation
426            return true;
427        }
428        else
429        {
430            // return the failure of the sc operation
431            return false;
432        }
433    }
434
435    ////////////////////////////////////////////////////////////////////////////
[482]436    /*
[291]437    inline void sw(const addr_t ad)
438    //  This method checks if there is a valid registration for the given
439    //  address and, in case of hit, invalidates the registration
440    {
441        // increment the sw access counter (for stats)
442        m_cpt_sw++;
443        // hit addr ?
444        // YES
445        //      inval registration
446        // NO
447        //      nothing
448
449        //  Is there a registration for the given address ?
450        int pos = hitAddr(ad);
451        //  If there is one, invalidate it
452        if(pos >= 0) r_val[pos] = false;
[482]453    }
454    */
[523]455    inline void sw(const addr_t ad_min, const addr_t ad_max)
[482]456    //  This method checks if there is / are valid registration(s) for the given
457    //  range and, in case of hit(s), invalidates the registration(s)
458    {
459        // increment the sw access counter (for stats)
460        m_cpt_sw++;
461        // hit range ?
462        // YES
463        //      inval registration(s)
464        // NO
465        //      nothing
[291]466
[482]467        // for every address in the given range ...
[524]468        for (addr_t i = ad_min; i <= ad_max; i+=4)
[482]469        {
470            //  Is there a registration for the given address ?
[523]471            int pos = hitAddr(i);
472
[482]473            //  If there is one, invalidate it
474            if (pos >= 0)
475            {
476                r_val[pos] = false;
477            }
478        }
[291]479    }
480
481    ////////////////////////////////////////////////////////////////////////////
482    /*
483    void fileTrace(FILE* file)
484    {
485    }
486    */
487
488    ////////////////////////////////////////////////////////////////////////////
489    inline void print_trace(std::ostream& out = std::cout)
490    {
491        out <<  " ___________________________________" << std::endl
492            <<  "| " << std::setw(33) << "generic_llsc_global_table" << " |" << std::endl
493            <<  "| " << std::setw(33) << name << " |" << std::endl
494            <<  " ===================================" << std::endl
495            <<  "| "
496            <<  std::setw(11) << "addr"   << " | "
497            <<  std::setw(11) << "key"    << " | "
498            <<  std::setw(5)  << "val"
499            << " |" << std::endl
500            <<  " -----------------------------------" << std::endl;
501        for ( size_t i = 0; i < nb_slots ; i++ )
502        {
503            out << "| "
504                << std::showbase
505                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
506                << std::noshowbase
507                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
508                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
509        }
510        out <<  " -----------------------------------" << std::endl
511            << std::noshowbase << std::dec << std::endl ;
512    }
513
514    ////////////////////////////////////////////////////////////////////////////
515    inline void print_stats(std::ostream& out = std::cout)
516    {
517        out << "# of ll accesses : " << m_cpt_ll            << std::endl
518            << "# of ll updates  : " << m_cpt_ll_update     << std::endl
519            << "# of sc accesses : " << m_cpt_sc            << std::endl
520            << "# of sc success  : " << m_cpt_sc_success    << std::endl
521            << "# of sw accesses : " << m_cpt_sw            << std::endl
522            << "# of evictions   : " << m_cpt_evic          << std::endl ;
523    }
524
525};
526
527} // end namespace soclib
528
529#endif
530
531// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
Note: See TracBrowser for help on using the repository browser.