source: soft/giet_vm/giet_libs/user_lock.c @ 722

Last change on this file since 722 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
  • Property svn:executable set to *
File size: 13.8 KB
RevLine 
[461]1//////////////////////////////////////////////////////////////////////////////////
2// File     : user_lock.c         
3// Date     : 01/12/2014
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6///////////////////////////////////////////////////////////////////////////////////
7// The user_lock.c and user_lock.h files are part of the GIET-VM nano-kernel.
8///////////////////////////////////////////////////////////////////////////////////
9
10#include "user_lock.h"
[709]11#include "malloc.h"
[461]12#include "giet_config.h"
13#include "stdio.h"
14
15//////////////////////////////////////////////////////////////////////////////////
[709]16//                atomic access functions
[461]17//////////////////////////////////////////////////////////////////////////////////
[709]18
19//////////////////////////////////////////////////
[461]20unsigned int atomic_increment( unsigned int*  ptr,
21                               unsigned int   increment )
22{
23    unsigned int value;
24
25    asm volatile (
26        "1234:                         \n"
27        "move $10,   %1                \n"   /* $10 <= ptr               */
28        "move $11,   %2                \n"   /* $11 <= increment         */
29        "ll   $12,   0($10)            \n"   /* $12 <= *ptr              */
30        "addu $13,   $11,    $12       \n"   /* $13 <= *ptr + increment  */
31        "sc   $13,   0($10)            \n"   /* M[ptr] <= new            */ 
32        "beqz $13,   1234b             \n"   /* retry if failure         */
33        "move %0,    $12               \n"   /* value <= *ptr if success */
34        : "=r" (value) 
35        : "r" (ptr), "r" (increment)
36        : "$10", "$11", "$12", "$13", "memory" );
37
38    return value;
39}
40
41///////////////////////////////////////////////////////////////////////////////////
[709]42//               simple lock access functions
[461]43///////////////////////////////////////////////////////////////////////////////////
[709]44
45//////////////////////////////////////
[461]46void lock_acquire( user_lock_t* lock ) 
47{
48    // get next free slot index from user_lock
49    unsigned int ticket = atomic_increment( &lock->free, 1 );
50
51#if GIET_DEBUG_USER_LOCK
52unsigned int    x;
53unsigned int    y;
54unsigned int    lpid;
55giet_proc_xyp( &x, &y, &lpid );
[709]56giet_tty_printf("\n[USER_LOCK DEBUG] lock_acquire() : P[%d,%d,%d] get ticket = %d"
[461]57                " for lock %x at cycle %d (current = %d / free = %d)\n",
58                x, y, lpid, ticket, 
59                (unsigned int)lock, giet_proctime(), lock->current, lock->free );
60#endif
61
62    // poll the current slot index
63    asm volatile("1793:                       \n"
64                 "lw   $10,  0(%0)            \n"
65                 "move $11,  %1               \n"
66                 "bne  $10,  $11,  1793b      \n"
67                 :
68                 : "r"(lock), "r"(ticket)
69                 : "$10", "$11" );
70               
71#if GIET_DEBUG_USER_LOCK
[709]72giet_tty_printf("\n[USER_LOCK DEBUG] lock_acquire() : P[%d,%d,%d] get lock %x"
[461]73                " at cycle %d (current = %d / free = %d)\n",
74                x, y, lpid, (unsigned int)lock, 
75                giet_proctime(), lock->current, lock->free );
76#endif
77
78}
79
[709]80//////////////////////////////////////
[461]81void lock_release( user_lock_t* lock ) 
82{
[501]83    asm volatile( "sync" );
[461]84
[501]85    lock->current = lock->current + 1;
[461]86
87#if GIET_DEBUG_USER_LOCK
88unsigned int    x;
89unsigned int    y;
90unsigned int    lpid;
91giet_proc_xyp( &x, &y, &lpid );
[709]92giet_tty_printf("\n[USER_LOCK DEBUG] lock_release() : P[%d,%d,%d] release lock %x"
[461]93                " at cycle %d (current = %d / free = %d)\n",
94                x, y, lpid, (unsigned int)lock, 
95                giet_proctime(), lock->current, lock->free );
96#endif
97
98}
99
[709]100///////////////////////////////////
[461]101void lock_init( user_lock_t* lock )
102{
103    lock->current = 0;
104    lock->free    = 0;
105
106#if GIET_DEBUG_USER_LOCK
107unsigned int    x;
108unsigned int    y;
109unsigned int    lpid;
110giet_proc_xyp( &x, &y, &lpid );
[709]111giet_tty_printf("\n[USER_LOCK DEBUG] lock_init() : P[%d,%d,%d] init lock %x"
[461]112                " at cycle %d (current = %d / free = %d)\n",
113                x, y, lpid, (unsigned int)lock,
114                giet_proctime(), lock->current, lock->free );
115#endif
116
117}
118
[709]119///////////////////////////////////////////////////////////////////////////////////
120//               SQT lock access functions
121///////////////////////////////////////////////////////////////////////////////////
[461]122
[709]123//////////////////////////////////////////////////
124static void sqt_lock_build( sqt_lock_t*      lock,      // pointer on the SQT lock
125                            unsigned int     x,         // node X coordinate
126                            unsigned int     y,         // node Y coordinate
127                            unsigned int     level,     // node level
128                            sqt_lock_node_t* parent,    // pointer on parent node
129                            unsigned int     xmax,      // SQT X size
130                            unsigned int     ymax )     // SQT Y size
131{
132
133#if GIET_DEBUG_USER_LOCK
134unsigned int    px;
135unsigned int    py;
136unsigned int    pl;
137giet_proc_xyp( &px, &py, &pl );
138#endif
139
140    // get target node pointer
141    sqt_lock_node_t* node = lock->node[x][y][level];
142   
143    if (level == 0 )        // terminal case
144    {
145        // initializes target node
146        node->current  = 0;   
147        node->free     = 0;
148        node->level    = 0;
149        node->parent   = parent;
150        node->child[0] = NULL;
151        node->child[1] = NULL;
152        node->child[2] = NULL;
153        node->child[3] = NULL;
154
155#if GIET_DEBUG_USER_LOCK
156giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_build() : "
157                "P[%d,%d,%d] initialises SQT node[%d,%d,%d] = %x :\n"
158                " parent = %x / child0 = %x / child1 = %x / child2 = %x / child3 = %x\n",
159                px , py , pl , x , y , level , (unsigned int)node ,
160                (unsigned int)node->parent , 
161                (unsigned int)node->child[0] , 
162                (unsigned int)node->child[1] , 
163                (unsigned int)node->child[2] , 
164                (unsigned int)node->child[3] );
165#endif
166
167    }
168    else                   // non terminal case
169    {
170        unsigned int cx[4];      // x coordinate for children
171        unsigned int cy[4];      // y coordinate for children
172        unsigned int i;          // child index
173
174        // the child0 coordinates are equal to the parent coordinates
175        // other childs coordinates are incremented depending on the level value
176        cx[0] = x;
177        cy[0] = y;
178
179        cx[1] = x + (1 << (level-1));
180        cy[1] = y;
181
182        cx[2] = x;
183        cy[2] = y + (1 << (level-1));
184
185        cx[3] = x + (1 << (level-1));
186        cy[3] = y + (1 << (level-1));
187
188        // initializes target node
189        for ( i = 0 ; i < 4 ; i++ )
190        {
191            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
192                node->child[i] = lock->node[cx[i]][cy[i]][level-1];
193            else 
194                node->child[i] = NULL;
195        }
196        node->current  = 0;
197        node->free     = 0;
198        node->level    = level;
199        node->parent   = parent;
200
201#if GIET_DEBUG_USER_LOCK
202giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_init() : "
203                "P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
204                " parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
205                px , py , pl , x , y , level , 
206                (unsigned int)node->parent , 
207                (unsigned int)node->child[0] , 
208                (unsigned int)node->child[1] , 
209                (unsigned int)node->child[2] , 
210                (unsigned int)node->child[3] );
211#endif
212
213       // recursive calls for children nodes
214        for ( i = 0 ; i < 4 ; i++ )
215        {
216            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
217                sqt_lock_build( lock, 
218                                 cx[i], 
219                                 cy[i], 
220                                 level-1, 
221                                 node, 
222                                 xmax, 
223                                 ymax );
224        }
225    }
226}  // end _sqt_lock_build()
227
228
229
230//////////////////////////////////////
231void sqt_lock_init( sqt_lock_t*  lock,
232                    unsigned int x_size,      // number of clusters in a row
233                    unsigned int y_size,      // number of clusters in a col
234                    unsigned int nthreads )   // threads per clusters
235{
236    // check parameters
237    if ( x_size > 16  ) giet_pthread_exit("SQT LOCK ERROR : x_size too large");
238    if ( y_size > 16  ) giet_pthread_exit("SQT LOCK ERROR : y_size too large");
239    if ( nthreads > 8 ) giet_pthread_exit("SQT LOCK ERROR : nthreads too large");
240   
241    // compute SQT levels
242    unsigned int levels; 
243    unsigned int z = (x_size > y_size) ? x_size : y_size;
244    levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5;
245
246#if GIET_DEBUG_USER_LOCK
247unsigned int    px;
248unsigned int    py;
249unsigned int    pp;
250giet_proc_xyp(&px, &py, &pp);
251unsigned int side   = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 4 : (z < 9) ? 8 : 16;
252giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_init() : "
253                "P[%d,%d%d] makes sqt_nodes allocation for lock %x\n"
254                " x_size = %d / y_size = %d / levels = %d / side = %d\n",
255                px, py, pp, (unsigned int) lock, x_size , y_size , levels , side );
256#endif
257
258   
259    unsigned int x;              // x coordinate for one SQT node
260    unsigned int y;              // y coordinate for one SQT node
261    unsigned int l;              // level for one SQT node
262
263    for ( x = 0 ; x < x_size ; x++ )
264    {
265        for ( y = 0 ; y < y_size ; y++ )
266        {
267            for ( l = 0 ; l < levels ; l++ )             // level 0 nodes
268            {
269               
270                if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) ||
271                     ( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) ||
272                     ( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) ||
273                     ( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) ||
274                     ( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
275                 {
276                     lock->node[x][y][l] = 
277                     (sqt_lock_node_t*)remote_malloc( sizeof(sqt_lock_node_t),
278                                                       x, y );
279
280#if GIET_DEBUG_USER_LOCK
281giet_tty_printf("\n[USER_LOCK DEBUG] squt_lock_init() : "
282                "P[%d,%d,%d] allocates SQT node[%d,%d,%d] = %x\n",
283                px , py , pp , x , y , l , (unsigned int)lock->node[x][y][l] );
284#endif
285                 }
286            }
287        }
288    }
289           
290    // recursively initialize all SQT nodes from root to bottom
291    sqt_lock_build( lock,
292                     0,
293                     0,
294                     levels-1,
295                     NULL,
296                     x_size,
297                     y_size );
298
299    asm volatile ("sync" ::: "memory");
300
301#if GIET_DEBUG_USER_LOCK
302giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_init() : "
303                "P[%d,%d,%d] completes SQT nodes initialisation\n", px, py, pp); 
304#endif
305
306} // end sqt_lock_init()
307
308
309//////////////////////////////////////////////////
310static void sqt_lock_take( sqt_lock_node_t* node )
311{
312    // get next free ticket from local lock
313    unsigned int ticket = atomic_increment( &node->free, 1 );
314
315#if GIET_DEBUG_USER_LOCK
316unsigned int    x;
317unsigned int    y;
318unsigned int    l;
319giet_proc_xyp(&x, &y, &l);
320giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_take() : "
321                "P[%d,%d,%d] get ticket %d for SQT lock %x"
322                " / level = %d / current = %d / free = %d\n",
323                x , y , l , ticket , (unsigned int)node ,
324                node->level , node->current , node->free );
325#endif
326
327    // poll the local lock current index
328    while ( (*(volatile unsigned int *)( &node->current )) != ticket ) asm volatile( "nop" );
329
330#if GIET_DEBUG_USER_LOCK
331giet_tty_printf("\n[DEBUG SQT_LOCK] sqt_lock_take() : "
332                "P[%d,%d,%d] get SQT lock %x"
333                " / level = %d / current = %d / free = %d\n",
334                x , y , l , (unsigned int)node ,
335                node->level , node->current , node->free );
336#endif
337
338    // try to take the parent node lock until top is reached
339    if ( node->parent != NULL ) sqt_lock_take( node->parent );
340
341} // end _sqt_lock_take()
342
343
344//////////////////////////////////////////
345void sqt_lock_acquire( sqt_lock_t*  lock )
346{
347    unsigned int x;
348    unsigned int y;
349    unsigned int p;
350
351    // get cluster coordinates
352    giet_proc_xyp( &x, &y, &p );
353
354#if GIET_DEBUG_USER_LOCK
355giet_tty_printf("\n[DEBUG SQT_LOCK] sqt_lock_acquire() : "
356                "P[%d,%d,%d] try to take lock = %x / lock_node = %x\n",
357                x, y, p, lock, lock->node[x][y][0] );
358#endif
359
360    // try to recursively take the distributed locks (from bottom to top)
361    sqt_lock_take( lock->node[x][y][0] );
362}
363
364//////////////////////////////////////////////////
365static void sqt_lock_give( sqt_lock_node_t* node )
366{
367    // release the local lock
368    node->current = node->current + 1;
369
370#if GIET_DEBUG_USER_LOCK
371unsigned int    x;
372unsigned int    y;
373unsigned int    l;
374giet_proc_xyp(&x, &y, &l);
375giet_tty_printf("\n[USER_LOCK DEBUG] sqt_lock_give() : "
376                "P[%d,%d,%d] release SQT lock_node %x"
377                " / level = %d / current = %d / free = %d\n",
378                x , y , l , (unsigned int)node, 
379                node->level , node->current , node->free );
380#endif
381
382    // reset parent node until top is reached
383    if ( node->parent != NULL ) sqt_lock_give( node->parent );
384
385} // end _sqt_lock_give()
386
387//////////////////////////////////////////
388void sqt_lock_release( sqt_lock_t*  lock )
389{
390    asm volatile ( "sync" );   // for consistency
391
392    unsigned int x;
393    unsigned int y;
394    unsigned int p;
395    // get cluster coordinates
396    giet_proc_xyp( &x, &y, &p );
397
398    // recursively reset the distributed locks (from bottom to top)
399    sqt_lock_give( lock->node[x][y][0] );
400}
401
402
[461]403// Local Variables:
404// tab-width: 4
405// c-basic-offset: 4
406// c-file-offsets:((innamespace . 0)(inline-open . 0))
407// indent-tabs-mode: nil
408// End:
409// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
410
Note: See TracBrowser for help on using the repository browser.