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

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

Bugfix in vci_mem_cache and generic_llsc_global_table:

  • The Store Conditional commmand was not performed atomically in some special cases. To solve this, a new operation has been introduced in the LL/SC table (check operation) which allows

to check if a SC operation is atomic or not without erasing the

reservation on the LL/SC table.

The reservation on the LL/SC table will be erased once the SC
command is completely treated:

  • A GET request has been inserted on the TRT when MISS.
  • An UPDATE request has been inserted on the UPT when MULTI

UPDATE needed.

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