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

Last change on this file since 730 was 709, checked in by alain, 9 years ago

Major release: Change the task model to implement the POSIX threads API.

  • The shell "exec" and "kill" commands can be used to activate/de-activate the applications.
  • The "pause", "resume", and "context" commands can be used to stop, restart, a single thtead or to display the thread context.

This version has been tested on the following multi-threaded applications,
that have been modified to use the POSIX threads:

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