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

Last change on this file since 514 was 514, checked in by meunier, 9 years ago

More memory cleaning for valgrind (generic_llsc_global_table, vci_block_device_tsar)

File size: 17.9 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 <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
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
297    public:
298
299    ////////////////////////////////////////////////////////////////////////////
300    GenericLLSCGlobalTable( const std::string   &n = "llsc_global_table" )
301    :   name(n)
302    {
303        #define L2 soclib::common::uint32_log2
304        assert(nb_procs > 1); 
305        assert((int)nb_slots >= L2(nb_procs));
306        #undef L2
307        init();
308        init_block_mask();
309    }
310
311    ////////////////////////////////////////////////////////////////////////////
312    ~GenericLLSCGlobalTable()
313    {
314    }
315
316    ////////////////////////////////////////////////////////////////////////////
317    //  This function initializes the table (all slots empty)
318    inline void init()
319    {
320        // making all slots available by reseting all valid bits
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);
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    ////////////////////////////////////////////////////////////////////////////
436    /*
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;
453    }
454    */
455    inline void sw(const addr_t nline, unsigned int min, unsigned int max)
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
466
467        // for every address in the given range ...
468        for (unsigned int i = min; i <= max; i++)
469        {
470            //  Is there a registration for the given address ?
471            int pos = hitAddr(nline + i * 4);
472            //  If there is one, invalidate it
473            if (pos >= 0)
474            {
475                r_val[pos] = false;
476            }
477        }
478    }
479
480    ////////////////////////////////////////////////////////////////////////////
481    /*
482    void fileTrace(FILE* file)
483    {
484    }
485    */
486
487    ////////////////////////////////////////////////////////////////////////////
488    inline void print_trace(std::ostream& out = std::cout)
489    {
490        out <<  " ___________________________________" << std::endl
491            <<  "| " << std::setw(33) << "generic_llsc_global_table" << " |" << std::endl
492            <<  "| " << std::setw(33) << name << " |" << std::endl
493            <<  " ===================================" << std::endl
494            <<  "| "
495            <<  std::setw(11) << "addr"   << " | "
496            <<  std::setw(11) << "key"    << " | "
497            <<  std::setw(5)  << "val"
498            << " |" << std::endl
499            <<  " -----------------------------------" << std::endl;
500        for ( size_t i = 0; i < nb_slots ; i++ )
501        {
502            out << "| "
503                << std::showbase
504                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
505                << std::noshowbase
506                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
507                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
508        }
509        out <<  " -----------------------------------" << std::endl
510            << std::noshowbase << std::dec << std::endl ;
511    }
512
513    ////////////////////////////////////////////////////////////////////////////
514    inline void print_stats(std::ostream& out = std::cout)
515    {
516        out << "# of ll accesses : " << m_cpt_ll            << std::endl
517            << "# of ll updates  : " << m_cpt_ll_update     << std::endl
518            << "# of sc accesses : " << m_cpt_sc            << std::endl
519            << "# of sc success  : " << m_cpt_sc_success    << std::endl
520            << "# of sw accesses : " << m_cpt_sw            << std::endl
521            << "# of evictions   : " << m_cpt_evic          << std::endl ;
522    }
523
524};
525
526} // end namespace soclib
527
528#endif
529
530// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
Note: See TracBrowser for help on using the repository browser.