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

Last change on this file was 1019, checked in by cfuguet, 8 years ago

Fixing some warnings for new compiler's versions

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