Ignore:
Timestamp:
Dec 12, 2014, 4:55:06 PM (10 years ago)
Author:
alain
Message:

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:
1 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/giet_common/locks.c

    r455 r466  
    88#include "locks.h"
    99#include "giet_config.h"
     10#include "hard_config.h"
    1011#include "utils.h"
     12#include "tty0.h"
     13#include "kernel_malloc.h"
    1114
    1215///////////////////////////////////////////////////
    … …  
    3235}
    3336
    34 ////////////////////////////////////
    35 void _lock_init( spin_lock_t* lock )
    36 {
    37     lock->current = 0;
    38     lock->free    = 0;
    39 
    40 #if GIET_DEBUG_SYS_LOCK
     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
    4146unsigned int    gpid = _get_procid();
    4247unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
    4348unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
    4449unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
    45 _printf("\n[SYS_LOCK DEBUG] P[%d,%d,%d] init lock %x"
    46                 " at cycle %d (current = %d / free = %d)\n",
    47                 x, y, l, (unsigned int)lock,
    48                 _get_proctime(), lock->current, lock->free );
    49 #endif
    50 
    51 }
    52 
    53 
    54 ////////////////////////////////////////
    55 void _lock_acquire( spin_lock_t* lock )
    56 {
    57     // get next free slot index fromlock
    58     unsigned int ticket = _atomic_increment( &lock->free, 1 );
    59 
    60 #if GIET_DEBUG_SYS_LOCK
    61 unsigned int    gpid = _get_procid();
    62 unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
    63 unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
    64 unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
    65 _printf("\n[SYS_LOCK DEBUG] P[%d,%d,%d] get ticket = %d"
    66                 " for lock %x at cycle %d (current = %d / free = %d)\n",
    67                 x, y, l, ticket,
    68                 (unsigned int)lock, _get_proctime(), lock->current, lock->free );
    69 #endif
    70 
    71 
    72     // poll the spin_lock current slot index
    73     asm volatile("5678:                   \n"
    74                  "lw   $10,  0(%0)        \n"
    75                  "move $11,  %1           \n"
    76                  "bne  $10,  $11,  5678b  \n"
    77                  :
    78                  : "r"(lock), "r"(ticket)
    79                  : "$10", "$11" );
    80 
    81 #if GIET_DEBUG_SYS_LOCK
    82 _printf("\n[SYS_LOCK DEBUG] P[%d,%d,%d] get lock = %x"
    83                 " at cycle %d (current = %d / free = %d)\n",
    84                 x, y, l, (unsigned int)lock,
    85                 _get_proctime(), lock->current, lock->free );
    86 #endif
    87 
    88 }
    89 
    90 ////////////////////////////////////////
    91 void _lock_release( spin_lock_t* lock )
    92 {
    93     unsigned int current = lock->current;
    94 
    95     if ( current == (GIET_LOCK_MAX_TICKET - 1) ) current = 0;
    96     else                                         current = current + 1;
    97 
    98     asm volatile ( "sync                    \n"   /* for consistency                  */
    99                    "sw   %1,    0(%0)       \n"   /* release lock                     */
    100                    :
    101                    : "r"(lock), "r"(current)
    102                    : "memory" );
    103    
    104 
    105 #if GIET_DEBUG_SYS_LOCK
    106 unsigned int    gpid = _get_procid();
    107 unsigned int    x    = gpid >> (Y_WIDTH + P_WIDTH);
    108 unsigned int    y    = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
    109 unsigned int    l    = gpid & ((1<<P_WIDTH)-1);
    110 _printf("\n[SYS_LOCK DEBUG] P[%d,%d,%d] release lock = %x"
    111                 " at cycle %d (current = %d / free = %d)\n",
    112                 x, y, l, (unsigned int)lock,
    113                 _get_proctime(), lock->current, lock->free );
    114 #endif
    115 
    116 }
    117 
    118 
    119 
    120 
    121 
    122 
    123 
    124 
    125 ////////////////////////////////////////////////
    126 void _simple_lock_acquire( simple_lock_t* lock )
    127 {
     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
    12854    asm volatile ( "1515:                   \n"
    12955                       "lw   $2,    0(%0)       \n"   /* $2 <= lock current value         */
    … …  
    13763                   : "r"(lock)
    13864                   : "$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
    13971}
    14072
    … …  
    14779                   : "r"(lock)
    14880                   : "memory" );
    149 }
    150 
     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}
    151488
    152489// Local Variables:
Note: See TracChangeset for help on using the changeset viewer.