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

Last change on this file was 1019, checked in by cfuguet, 11 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.