source: soft/giet_vm/giet_common/kernel_locks.c @ 653

Last change on this file since 653 was 632, checked in by alain, 9 years ago

Introduce two new atomic read-the-write functions, that can be used
to set or reset a bit field in a shared 32 bits word:

_atomic_or()
_atpmic_and()
File size: 18.5 KB
Line 
1///////////////////////////////////////////////////////////////////////////////////
2// File     : kernel_locks.c
3// Date     : 01/12/2014
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6///////////////////////////////////////////////////////////////////////////////////
7
8#include "kernel_locks.h"
9#include "giet_config.h"
10#include "hard_config.h"
11#include "utils.h"
12#include "tty0.h"
13#include "kernel_malloc.h"
14#include "io.h"
15
16///////////////////////////////////////////////////
17unsigned int _atomic_increment( unsigned int* ptr,
18                                int           increment )
19{
20    unsigned int value;
21
22    asm volatile (
23        "1234:                         \n"
24        "move $10,   %1                \n"   /* $10 <= ptr               */
25        "move $11,   %2                \n"   /* $11 <= increment         */
26        "ll   $12,   0($10)            \n"   /* $12 <= *ptr              */
27        "addu $13,   $11,    $12       \n"   /* $13 <= *ptr + increment  */
28        "sc   $13,   0($10)            \n"   /* *ptr <= $12              */ 
29        "beqz $13,   1234b             \n"   /* retry if failure         */
30        "move %0,    $12               \n"   /* value <= *ptr if success */
31        : "=r" (value) 
32        : "r" (ptr), "r" (increment)
33        : "$10", "$11", "$12", "$13", "memory" );
34
35    return value;
36}
37
38////////////////////////////////////
39void _atomic_or( unsigned int* ptr,
40                 unsigned int  mask )
41{
42    asm volatile (
43        "1789:                         \n"
44        "move $10,   %0                \n"   /* $10 <= ptr               */
45        "move $11,   %1                \n"   /* $11 <= mask              */
46        "ll   $12,   0($10)            \n"   /* $12 <= *ptr              */
47        "or   $12,   $11,    $12       \n"   /* $12 <= *ptr | mask       */
48        "sc   $12,   0($10)            \n"   /* *ptr <= $12              */ 
49        "beqz $12,   1789b             \n"   /* retry if failure         */
50        "nop                           \n" 
51        :
52        : "r" (ptr), "r" (mask)
53        : "$10", "$11", "$12", "memory" );
54}
55
56////////////////////////////////////
57void _atomic_and( unsigned int* ptr,
58                  unsigned int  mask )
59{
60    asm volatile (
61        "1945:                         \n"
62        "move $10,   %0                \n"   /* $10 <= ptr               */
63        "move $11,   %1                \n"   /* $11 <= mask              */
64        "ll   $12,   0($10)            \n"   /* $12 <= *ptr              */
65        "and  $12,   $11,    $12       \n"   /* $13 <= *ptr & mask       */
66        "sc   $12,   0($10)            \n"   /* *ptr <= new              */ 
67        "beqz $12,   1945b             \n"   /* retry if failure         */
68        "nop                           \n" 
69        :
70        : "r" (ptr), "r" (mask)
71        : "$10", "$11", "$12", "memory" );
72}
73
74
75///////////////////////////////////////////////////////////////////////////////////
76//      Simple lock access functions
77///////////////////////////////////////////////////////////////////////////////////
78
79////////////////////////////////////////////////
80void _simple_lock_acquire( simple_lock_t* lock )
81{
82
83#if GIET_DEBUG_SIMPLE_LOCK
84unsigned int    gpid = _get_procid();
85unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
86unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
87unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
88_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] enters acquire() at cycle %d\n",
89               x , y , l , _get_proctime() );
90#endif
91
92    asm volatile ( "1515:                   \n"
93                       "lw   $2,    0(%0)       \n"
94                       "bnez $2,    1515b       \n"
95                   "ll   $2,    0(%0)       \n"
96                   "bnez $2,    1515b       \n"
97                   "li   $3,    1           \n"
98                   "sc   $3,    0(%0)       \n"
99                   "beqz $3,    1515b       \n"
100                   :
101                   : "r"(lock)
102                   : "$2", "$3", "memory" );
103
104#if GIET_DEBUG_SIMPLE_LOCK
105_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] exit acquire() at cycle %d\n",
106               x , y , l , _get_proctime() );
107#endif
108
109}
110
111////////////////////////////////////////////////
112void _simple_lock_release( simple_lock_t* lock )
113{
114    asm volatile ( "sync" );   // for consistency
115
116    lock->value = 0;
117
118#if GIET_DEBUG_SIMPLE_LOCK
119unsigned int    gpid = _get_procid();
120unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
121unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
122unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
123_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] release() at cycle %d\n",
124               x , y , l , _get_proctime() );
125#endif
126
127}
128
129
130///////////////////////////////////////////////////////////////////////////////////
131//      Queuing Lock access functions
132///////////////////////////////////////////////////////////////////////////////////
133
134/////////////////////////////////////////
135void _spin_lock_init( spin_lock_t* lock )
136{
137    lock->current = 0;
138    lock->free    = 0;
139
140#if GIET_DEBUG_SPIN_LOCK
141unsigned int    gpid = _get_procid();
142unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
143unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
144unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
145_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] initializes lock %x at cycle %d\n",
146               x, y, l, (unsigned int)lock, _get_proctime() );
147#endif
148
149}
150
151
152////////////////////////////////////////////
153void _spin_lock_acquire( spin_lock_t* lock )
154{
155    // get next free slot index fromlock
156    unsigned int ticket = _atomic_increment( &lock->free, 1 );
157
158#if GIET_DEBUG_SPIN_LOCK
159unsigned int    gpid = _get_procid();
160unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
161unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
162unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
163_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] get ticket %d for lock %x at cycle %d"
164               " / current = %d / free = %d\n",
165               x, y, l, ticket, (unsigned int)lock, _get_proctime(),
166               lock->current, lock->free );
167#endif
168
169    // poll the spin_lock current slot index
170    while ( ioread32( &lock->current ) != ticket ) asm volatile ("nop");
171
172#if GIET_DEBUG_SPIN_LOCK
173_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] get lock %x at cycle %d"
174               " / current = %d / free = %d\n",
175               x, y, l, (unsigned int)lock, _get_proctime(),
176               lock->current, lock->free );
177#endif
178
179}
180
181////////////////////////////////////////////
182void _spin_lock_release( spin_lock_t* lock )
183{
184    asm volatile ( "sync" );   // for consistency
185
186    lock->current = lock->current + 1;
187
188#if GIET_DEBUG_SPIN_LOCK
189_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] release lock %x at cycle %d"
190               " / current = %d / free = %d\n",
191               x, y, l, (unsigned int)lock, _get_proctime(),
192               lock->current, lock->free );
193#endif
194
195}
196
197
198
199///////////////////////////////////////////////////////////////////////////////////
200//      SQT lock access functions
201///////////////////////////////////////////////////////////////////////////////////
202
203///////////////////////////////////////////////////////////////////////////////////
204// This recursive function is used by the _sqt_lock_init() function
205// to initializes the SQT nodes (mainly the parent and child pointers).
206// It traverses the SQT from top to bottom.
207// The SQT can be uncomplete (when xmax or ymax are not power of 2),
208// and the recursion stops when the (x,y) coordinates exceed the footprint.
209///////////////////////////////////////////////////////////////////////////////////
210static 
211void _sqt_lock_build( sqt_lock_t*      lock,      // pointer on the SQT lock
212                      unsigned int     x,         // node X coordinate
213                      unsigned int     y,         // node Y coordinate
214                      unsigned int     level,     // node level
215                      sqt_lock_node_t* parent,    // pointer on parent node
216                      unsigned int     xmax,      // SQT X size
217                      unsigned int     ymax )     // SQT Y size
218{
219
220#if GIET_DEBUG_SQT_LOCK
221unsigned int    gpid = _get_procid();
222unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
223unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
224unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
225#endif
226
227    // get target node pointer
228    sqt_lock_node_t* node = lock->node[x][y][level];
229   
230    if (level == 0 )        // terminal case
231    {
232        // initializes target node
233        node->current  = 0;   
234        node->free     = 0;
235        node->level    = 0;
236        node->parent   = parent;
237        node->child[0] = NULL;
238        node->child[1] = NULL;
239        node->child[2] = NULL;
240        node->child[3] = NULL;
241
242#if GIET_DEBUG_SQT_LOCK
243_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
244      " parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
245      px , py , pl , x , y , level , 
246      (unsigned int)node->parent , 
247      (unsigned int)node->child[0] , 
248      (unsigned int)node->child[1] , 
249      (unsigned int)node->child[2] , 
250      (unsigned int)node->child[3] );
251#endif
252
253    }
254    else                   // non terminal case
255    {
256        unsigned int cx[4];      // x coordinate for children
257        unsigned int cy[4];      // y coordinate for children
258        unsigned int i;          // child index
259
260        // the child0 coordinates are equal to the parent coordinates
261        // other childs coordinates are incremented depending on the level value
262        cx[0] = x;
263        cy[0] = y;
264
265        cx[1] = x + (1 << (level-1));
266        cy[1] = y;
267
268        cx[2] = x;
269        cy[2] = y + (1 << (level-1));
270
271        cx[3] = x + (1 << (level-1));
272        cy[3] = y + (1 << (level-1));
273
274        // initializes target node
275        for ( i = 0 ; i < 4 ; i++ )
276        {
277            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
278                node->child[i] = lock->node[cx[i]][cy[i]][level-1];
279            else 
280                node->child[i] = NULL;
281        }
282        node->current  = 0;
283        node->free     = 0;
284        node->level    = level;
285        node->parent   = parent;
286
287#if GIET_DEBUG_SQT_LOCK
288_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
289      " parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
290      px , py , pl , x , y , level , 
291      (unsigned int)node->parent , 
292      (unsigned int)node->child[0] , 
293      (unsigned int)node->child[1] , 
294      (unsigned int)node->child[2] , 
295      (unsigned int)node->child[3] );
296#endif
297
298       // recursive calls for children nodes
299        for ( i = 0 ; i < 4 ; i++ )
300        {
301            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
302                _sqt_lock_build( lock, 
303                                 cx[i], 
304                                 cy[i], 
305                                 level-1, 
306                                 node, 
307                                 xmax, 
308                                 ymax );
309        }
310    }
311}  // end _sqt_lock_build()
312
313/////////////////////////////////////////////////////////////////////////////////
314// This external function initialises the distributed SQT lock.
315// It allocates memory for the distributed SQT nodes in clusters,
316// and initializes the SQT nodes pointers array (stored in cluster[0][0].
317// The SQT can be "uncomplete" as SQT lock nodes are only build in clusters
318// containing processors.
319// The actual number of SQT locks nodes in a cluster[x][y] depends on (x,y):
320// At least 1 node / at most 5 nodes per cluster:
321// - lock arbitrating between all processors of   1 cluster  has level 0,
322// - lock arbitrating between all processors of   4 clusters has level 1,
323// - lock arbitrating between all processors of  16 clusters has level 2,
324// - lock arbitrating between all processors of  64 clusters has level 3,
325// - lock arbitrating between all processors of 256 clusters has level 4,
326/////////////////////////////////////////////////////////////////////////////////
327void _sqt_lock_init( sqt_lock_t*  lock )
328{
329    unsigned int levels;
330    unsigned int xmax;
331    unsigned int ymax;
332
333    // compute the smallest SQT covering all processors
334    _get_sqt_footprint( &xmax, &ymax, &levels );
335
336
337#if GIET_DEBUG_SQT_LOCK
338unsigned int    gpid = _get_procid();
339unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
340unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
341unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
342_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT lock %x : \n"
343               " xmax = %d / ymax = %d / levels = %d\n",
344               px , py , pl , (unsigned int)lock , 
345               xmax , ymax , levels );
346#endif
347
348   
349    unsigned int x;              // x coordinate for one SQT node
350    unsigned int y;              // y coordinate for one SQT node
351    unsigned int l;              // level for one SQT node
352
353    for ( x = 0 ; x < xmax ; x++ )
354    {
355        for ( y = 0 ; y < ymax ; y++ )
356        {
357            for ( l = 0 ; l < levels ; l++ )             // level 0 nodes
358            {
359               
360                if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) ||
361                     ( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) ||
362                     ( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) ||
363                     ( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) ||
364                     ( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
365                 {
366                     lock->node[x][y][l] = 
367                     (sqt_lock_node_t*)_remote_malloc( sizeof(sqt_lock_node_t),
368                                                       x, y );
369
370#if GIET_DEBUG_SQT_LOCK
371_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] allocates SQT node[%d,%d,%d]"
372               " : vaddr = %x\n",
373               px , py , pl , x , y , l , (unsigned int)lock->node[x][y][l] );
374#endif
375                 }
376            }
377        }
378    }
379           
380    // recursively initialize all SQT nodes from root to bottom
381    _sqt_lock_build( lock,       // pointer on the SQT lock descriptor
382                     0,          // x coordinate
383                     0,          // y coordinate
384                     levels-1,   // level in SQT
385                     NULL,       // pointer on the parent node
386                     xmax,       // SQT footprint X size
387                     ymax );     // SQT footprint X size
388
389    asm volatile ("sync" ::: "memory");
390
391#if GIET_DEBUG_SQT_LOCK
392_nolock_printf("\n[DEBUG SQT_LOCK] SQT nodes initialisation completed\n"); 
393#endif
394
395} // end _sqt_lock_init()
396
397//////////////////////////////////////////////////////////////////////////////////
398// This recursive function is used by the sqt_lock_acquire() function to get
399// a distributed SQT lock: It tries to get each local queuing lock on the path
400// from bottom to top, and starting from bottom.
401// It is blocking : it polls each "partial lock until it can be taken.
402// The lock is finally obtained when all locks, at all levels are taken.
403//////////////////////////////////////////////////////////////////////////////////
404static 
405void _sqt_lock_take( sqt_lock_node_t* node )
406{
407    // get next free ticket from local lock
408    unsigned int ticket = _atomic_increment( &node->free, 1 );
409
410#if GIET_DEBUG_SQT_LOCK
411unsigned int    gpid = _get_procid();
412unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
413unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
414unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
415_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] get ticket %d for SQT lock %x"
416               " / level = %d / current = %d / free = %d\n",
417               x , y , l , ticket , (unsigned int)node ,
418               node->level , node->current , node->free );
419#endif
420
421    // poll the local lock current index
422    while ( ioread32( &node->current ) != ticket ) asm volatile( "nop" );
423
424#if GIET_DEBUG_SQT_LOCK
425_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] get SQT lock %x"
426               " / level = %d / current = %d / free = %d\n",
427               x , y , l , (unsigned int)node ,
428               node->level , node->current , node->free );
429#endif
430
431    // try to take the parent node lock until top is reached
432    if ( node->parent != NULL ) _sqt_lock_take( node->parent );
433
434} // end _sqt_lock_take()
435   
436//////////////////////////////////////////////////////////////////////////////////
437// This external function get thes SQT lock.
438// Returns only when the lock has been taken.
439/////////////////////////////////////////////////////////////////////////////////
440void _sqt_lock_acquire( sqt_lock_t*  lock )
441{
442    // get cluster coordinates
443    unsigned int gpid = _get_procid();
444    unsigned int x    = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<<X_WIDTH)-1);
445    unsigned int y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
446
447    // try to recursively take the distributed locks (from bottom to top)
448    _sqt_lock_take( lock->node[x][y][0] );
449}
450
451
452/////////////////////////////////////////////////////////////////////////////////
453// This recursive function is used by the sqt_lock_release() function to
454// release distributed SQT lock: It releases all local locks on the path from
455// bottom to top, using a normal read/write, and starting from bottom.
456/////////////////////////////////////////////////////////////////////////////////
457static 
458void _sqt_lock_give( sqt_lock_node_t* node )
459{
460    // release the local lock
461    node->current = node->current + 1;
462
463#if GIET_DEBUG_SQT_LOCK
464unsigned int    gpid = _get_procid();
465unsigned int    x   = gpid >> (Y_WIDTH + P_WIDTH);
466unsigned int    y   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
467unsigned int    l   = gpid & ((1<<P_WIDTH)-1);
468_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] release SQT lock %x"
469               " / level = %d / current = %d / free = %d\n",
470               x , y , l , (unsigned int)node, 
471               node->level , node->current , node->free );
472#endif
473
474    // reset parent node until top is reached
475    if ( node->parent != NULL ) _sqt_lock_give( node->parent );
476
477} // end _sqt_lock_give()
478
479
480/////////////////////////////////////////////////////////////////////////////////
481// This external function releases the SQT lock.
482/////////////////////////////////////////////////////////////////////////////////
483void _sqt_lock_release( sqt_lock_t*  lock )
484{
485    asm volatile ( "sync" );   // for consistency
486
487    // get cluster coordinates
488    unsigned int gpid = _get_procid();
489    unsigned int x    = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<<X_WIDTH)-1);
490    unsigned int y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
491
492    // recursively reset the distributed locks (from bottom to top)
493    _sqt_lock_give( lock->node[x][y][0] );
494}
495
496// Local Variables:
497// tab-width: 4
498// c-basic-offset: 4
499// c-file-offsets:((innamespace . 0)(inline-open . 0))
500// indent-tabs-mode: nil
501// End:
502// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
503
Note: See TracBrowser for help on using the repository browser.