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

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

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