source: soft/giet_vm/giet_common/locks.c @ 466

Last change on this file since 466 was 466, checked in by alain, 10 years ago

1) Introducing a hierarchical, distributed lock, implemented as a

Sliced Binary Tree (sbt_lock_t) in the locks.c and locks.h files.

2) Introducing a kernel level distributed, remote_malloc() service,

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