Ignore:
Timestamp:
Oct 11, 2018, 5:04:28 PM (6 years ago)
Author:
alain
Message:

New DQDT implementation supporting missing clusters
thanks to the cluster_info[x][y] array.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/kernel/kern/dqdt.c

    r564 r582  
    2525#include <hal_kernel_types.h>
    2626#include <hal_special.h>
     27#include <hal_macros.h>
    2728#include <hal_atomic.h>
    2829#include <hal_remote.h>
     
    4041extern chdev_directory_t  chdev_dir;  // defined in chdev.h / allocated in kernel_init.c
    4142
    42 /*
    4343///////////////////////////////////////////////////////////////////////////////////////////
    4444// This static recursive function traverse the DQDT quad-tree from root to bottom.
     
    4646static void dqdt_recursive_print( xptr_t  node_xp )
    4747{
    48         uint32_t i;
     48        uint32_t x;
     49        uint32_t y;
    4950    dqdt_node_t node;
    5051
     
    5960    if ( node.level > 0 )
    6061    {
    61         for ( i = 0 ; i < 4 ; i++ )
    62         {
    63             if ( node.children[i] != XPTR_NULL ) dqdt_recursive_print( node.children[i] );
     62        for ( x = 0 ; x < 2 ; x++ )
     63        {
     64            for ( y = 0 ; y < 2 ; y++ )
     65            {
     66                xptr_t iter_xp = node.children[x][y];
     67                if ( iter_xp != XPTR_NULL ) dqdt_recursive_print( iter_xp );
     68            }
    6469        }
    6570    }
    6671}
    67 */
    6872
    6973/////////////////////////
    7074void dqdt_display( void )
    7175{
    72     return;
    73 
    74 /*
    75     // build extended pointer on DQDT root node
    76         cluster_t * cluster = LOCAL_CLUSTER;
    77     uint32_t    level   = cluster->dqdt_root_level;
    78     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
     76    // get extended pointer on DQDT root node
     77        cluster_t * cluster = &cluster_manager;
     78    xptr_t      root_xp = cluster->dqdt_root_xp;
    7979
    8080    // get pointers on TXT0 chdev
     
    9595    dqdt_recursive_print( root_xp );
    9696
    97     // release lock
     97    // release TXT0 lock
    9898    remote_busylock_release( lock_xp );
    99 */
    100 
    101 }
    102 
    103 ////////////////////////////////////
    104 uint32_t dqdt_init( uint32_t x_size,
    105                     uint32_t y_size )
    106 {
    107     assert( ((x_size <= 32) && (y_size <= 32)) , "illegal mesh size\n");
     99}
     100
     101///////////////////////////////////////////////////////////////////////////////////////
     102// This static function initializes recursively, from top to bottom, the quad-tree
     103// infrastructure. The DQDT nodes are allocated as global variables in each local
     104//  cluster manager. At each level in the quad-tree, this function initializes the
     105// parent DQDT node in the cluster identified by the <cxy> and <level> arguments.
     106// A each level, it selects in each child macro-cluster the precise cluster where
     107// will be placed the the subtree root node, and call recursively itself to
     108// initialize the child node in this cluster.
     109///////////////////////////////////////////////////////////////////////////////////////
     110// @ node cxy  : cluster containing the node to initialize
     111// @ level     : level of node to be initialised
     112// @ parent_xp : extended pointer on the parent node
     113///////////////////////////////////////////////////////////////////////////////////////
     114static void dqdt_recursive_build( cxy_t    node_cxy,
     115                                  uint32_t level,
     116                                  xptr_t   parent_xp )
     117{
     118    assert( (level < 5) , __FUNCTION__, "illegal DQDT level %d\n", level );
     119 
     120    uint32_t node_x;         // node X coordinate
     121    uint32_t node_y;         // node Y coordinate
     122    uint32_t mask;           // to compute associated macro-cluster coordinates
     123    uint32_t node_base_x;    // associated macro_cluster X coordinate
     124    uint32_t node_base_y;    // associated macro_cluster y coordinate
     125    uint32_t half;           // associated macro-cluster half size
     126
     127    // get remote node cluster coordinates
     128    node_x = HAL_X_FROM_CXY( node_cxy );
     129    node_y = HAL_Y_FROM_CXY( node_cxy );
     130       
     131    // get macro-cluster mask and half-size
     132    mask   = (1 << level) - 1;
     133    half   = (level > 0) ? (1 << (level - 1)) : 0;
     134
     135    // get macro-cluster coordinates
     136    node_base_x = node_x & ~mask;
     137    node_base_y = node_y & ~mask;
     138
     139    // get pointer on local cluster manager
     140    cluster_t * cluster = LOCAL_CLUSTER;
     141
     142    // get local pointer on remote node to be initialized
     143    dqdt_node_t * node  = &cluster->dqdt_tbl[level];
     144
     145#if DEBUG_DQDT_INIT
     146printk("\n[DBG] %s : cxy(%d,%d) / level %d / mask %x / half %d / ptr %x\n",
     147__FUNCTION__, node_x, node_y, level, mask, half, node );
     148#endif
     149 
     150    // make remote node default initialisation
     151    hal_remote_memset( XPTR( node_cxy , node ) , 0 , sizeof( dqdt_node_t ) );
     152
     153    // recursive initialisation
     154    if( level == 0 )                      // terminal case
     155    {
     156        // update parent field
     157        hal_remote_s64( XPTR( node_cxy , &node->parent ) , parent_xp );
     158    }
     159    else                                  // non terminal
     160    {
     161        uint32_t x;
     162        uint32_t y;
     163        cxy_t    cxy;
     164        bool_t   found;
     165
     166        // update <level> in remote node
     167        hal_remote_s32( XPTR( node_cxy , &node->level ) , level );
     168
     169        // try to find a valid cluster in child[0][0] macro-cluster
     170        found = false;
     171        for( x = node_base_x ;
     172        (x < (node_base_x + half)) && (found == false) ; x++ )
     173        {
     174            for( y = node_base_y ;
     175            (y < (node_base_y + half)) && (found == false) ; y++ )
     176            {
     177                cxy = HAL_CXY_FROM_XY( x , y );
     178                if( cluster_is_active( cxy ) )
     179                {
     180                    // update <child[0][0]> in remote inode
     181                    hal_remote_s64( XPTR( node_cxy , &node->children[0][0] ),
     182                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     183
     184                    // udate <arity> in remote node
     185                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     186
     187                    // initialize recursively child[0][0] node
     188                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     189   
     190                    // exit loops
     191                    found = true;
     192                }
     193            }
     194        }
     195
     196        // try to find a valid cluster in child[0][1] macro-cluster
     197        found = false;
     198        for( x = node_base_x ;
     199        (x < (node_base_x + half)) && (found == false) ; x++ )
     200        {
     201            for( y = (node_base_y + half) ;
     202            (y < (node_base_y + (half<<2))) && (found == false) ; y++ )
     203            {
     204                cxy = HAL_CXY_FROM_XY( x , y );
     205                if( cluster_is_active( cxy ) )
     206                {
     207                    // update <child[0][1]> in remote inode
     208                    hal_remote_s64( XPTR( node_cxy , &node->children[0][1] ),
     209                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     210
     211                    // udate <arity> in remote node
     212                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     213
     214                    // initialize recursively child[0][1] node
     215                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     216   
     217                    // exit loops
     218                    found = true;
     219                }
     220            }
     221        }
     222           
     223        // try to find a valid cluster in child[1][0] macro-cluster
     224        found = false;
     225        for( x = (node_base_x + half) ;
     226        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
     227        {
     228            for( y = node_base_y ;
     229            (y < (node_base_y + half)) && (found == false) ; y++ )
     230            {
     231                cxy = HAL_CXY_FROM_XY( x , y );
     232                if( cluster_is_active( cxy ) )
     233                {
     234                    // update <child[1][0]> in remote inode
     235                    hal_remote_s64( XPTR( node_cxy , &node->children[1][0] ),
     236                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     237
     238                    // udate <arity> in remote node
     239                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     240
     241                    // initialize recursively child[1][0] node
     242                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     243   
     244                    // exit loops
     245                    found = true;
     246                }
     247            }
     248        }
     249
     250        // try to find a valid cluster in child[1][1] macro-cluster
     251        found = false;
     252        for( x = (node_base_x + half) ;
     253        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
     254        {
     255            for( y = (node_base_y + half) ;
     256            (y < (node_base_y + (half<<2))) && (found == false) ; y++ )
     257            {
     258                cxy = HAL_CXY_FROM_XY( x , y );
     259                if( cluster_is_active( cxy ) )
     260                {
     261                    // update <child[1][1]> in remote inode
     262                    hal_remote_s64( XPTR( node_cxy , &node->children[1][1] ),
     263                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     264
     265                    // udate <arity> in remote node
     266                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     267
     268                    // initialize recursively child[1][1] node
     269                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     270   
     271                    // exit loops
     272                    found = true;
     273                }
     274            }
     275        }
     276    }
     277}  // end dqdt_recursive_build()
     278
     279//////////////////////
     280void dqdt_init( void )
     281{
     282    // get x_size & y_size from cluster manager
     283    cluster_t * cluster = &cluster_manager;
     284    uint32_t    x_size  = cluster->x_size;
     285    uint32_t    y_size  = cluster->y_size;
     286
     287    assert( ((x_size <= 16) && (y_size <= 16)) , "illegal mesh size\n");
    108288 
    109289    // compute level_max
    110290    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
    111291    uint32_t  y_size_ext = POW2_ROUNDUP( y_size );
    112     uint32_t  size_ext   = MAX(x_size_ext , y_size_ext);
    113     uint32_t  level_max  = (bits_log2(size_ext * size_ext) >> 1) + 1;
    114 
    115 return level_max;
    116 
    117 /*
    118         dqdt_node_t * node;
    119     cxy_t         p_cxy;         // cluster coordinates for parent node
    120     cxy_t         c_cxy;         // cluster coordinates for child node
    121     uint32_t      level;         // node level in quad tree
    122     uint32_t      mask;          // mask on node coordinates to compute existence condition
    123     uint32_t      pmask;         // mask to compute parent coordinates from child coordinates
    124     cluster_t   * cluster;       // pointer on local cluster
    125 
    126     cluster_t   * cluster = LOCAL_CLUSTER;
    127 
    128     // get cluster coordinates
    129     uint32_t    x       = HAL_X_FROM_CXY( local_cxy );
    130     uint32_t    y       = HAL_Y_FROM_CXY( local_cxy );
    131 
    132     // loop on local dqdt nodes (at most one node per level)
    133     for( level = 0 ; level < level_max ; level++ )
    134     {
    135         // get pointer on the node to be initialised
    136         node = &cluster->dqdt_tbl[level];
    137 
    138         // set default values
    139         node->level       = level;
    140         node->arity       = 0;
    141         node->threads     = 0;
    142         node->pages       = 0;
    143         node->parent      = XPTR_NULL;
    144         node->children[0] = XPTR_NULL;
    145         node->children[1] = XPTR_NULL;
    146         node->children[2] = XPTR_NULL;
    147         node->children[3] = XPTR_NULL;
    148 
    149         // compute masks depending on level : 0x1, 0x3, 0x7, 0xF, 0x1F etc.
    150         mask  = (1<<level)-1;
    151         pmask = (1<<(level+1))-1;
    152 
    153         // check the node  existence condition at each level
    154         if( ((x & mask) == 0) && ((y & mask) == 0) )
    155         {
    156             // set parent extended pointer
    157             p_cxy = HAL_CXY_FROM_XY( (x & ~pmask) , (y & ~pmask) );
    158             node->parent = XPTR( p_cxy , &cluster->dqdt_tbl[level+1] );
    159 
    160             // set child[0] extended pointer (same [x,y] coordinates)
    161             if ( level > 0 )
    162             {
    163                 c_cxy = local_cxy;
    164                 node->children[0] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    165                 node->arity++;
    166             }
    167 
    168             // set child[1] extended pointer (coordinates may overflow)
    169             if ( (level > 0) && ((y + (1<<(level-1))) < y_size) )
    170             {
    171                 c_cxy = local_cxy + HAL_CXY_FROM_XY( 0 , (1<<(level-1) );
    172                 node->children[1] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1] );
    173                 node->arity++;
    174             }
    175 
    176             // set child[2] extended pointer (coordinates may overflow)
    177             if ( (level > 0) && ((x + (1<<(level-1))) < x_size) )
    178             {
    179                 c_cxy = local_cxy + HAL_CXY_FROM_XY( (1<<(level-1)) , 0 );
    180                 node->children[2] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    181                 node->arity++;
    182             }
    183 
    184             // set child[3] extended pointer (coordinates may overflow)
    185             if ( (level > 0) &&
    186                  ((x + (1<<(level-1))) < x_size) &&
    187                  ((y + (1<<(level-1))) < y_size) )
    188             {
    189                 c_cxy = local_cxy + HAL_CXY_FROM_XY( (1<<(level-1)) , (1<<(level-1) );
    190                 node->children[3] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    191                 node->arity++;
    192             }
    193         }  // end if existence condition
    194     }  // end for level
    195 
    196     return level_max;
    197 */
    198 
    199 } // end dqdt_init()
    200 
    201 /*
     292    uint32_t  size_ext   = MAX( x_size_ext , y_size_ext );
     293    uint32_t  level_max  = bits_log2( size_ext );
     294
     295    // each CP0 register the DQDT root in local cluster manager
     296    cluster->dqdt_root_xp = XPTR( 0 , &cluster->dqdt_tbl[level_max] );
     297
     298#if DEBUG_DQDT_INIT
     299if( local_cxy == 0 )
     300printk("\n[DBG] %s : x_size = %d / y_size = %d / level_max = %d\n",
     301__FUNCTION__, x_size, y_size, level_max );
     302#endif
     303   
     304    // only CP0 in cluster 0 call the recursive function to build the quad-tree
     305    if (local_cxy == 0) dqdt_recursive_build( local_cxy , level_max , XPTR_NULL );
     306
     307#if DEBUG_DQDT_INIT
     308if( local_cxy == 0 ) dqdt_display();
     309#endif
     310
     311}  // end dqdt_init()
     312
    202313///////////////////////////////////////////////////////////////////////////
    203314// This recursive function is called by the dqdt_update_threads() function.
     
    223334    if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
    224335}
    225 */
    226 
    227 /*
     336
    228337///////////////////////////////////////////////////////////////////////////
    229338// This recursive function is called by the dqdt_update_pages() function.
     
    249358    if ( parent != XPTR_NULL ) dqdt_propagate_pages( parent, increment );
    250359}
    251 */
    252360
    253361/////////////////////////////////////////////
    254 void dqdt_update_threads( int32_t increment __attribute__ ((__unused__)) )
    255 {
    256 
    257 return;
    258 
    259 /*
     362void dqdt_update_threads( int32_t increment )
     363{
    260364        cluster_t   * cluster = LOCAL_CLUSTER;
    261365    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
     
    266370    // propagate to DQDT upper levels
    267371    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment );
    268 */
    269 
    270372}
    271373
    272374///////////////////////////////////////////
    273 void dqdt_update_pages( int32_t increment  __attribute__ ((__unused__)) )
    274 {
    275 
    276 return;
    277 
    278 /*
     375void dqdt_update_pages( int32_t increment )
     376{
    279377        cluster_t   * cluster = LOCAL_CLUSTER;
    280378    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
     
    285383    // propagate to DQDT upper levels
    286384    if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment );
    287 */
    288 
    289 }
    290 
    291 /*
     385}
     386
    292387////////////////////////////////////////////////////////////////////////////////
    293388// This recursive function is called by both the dqdt_get_cluster_for_process()
     
    300395{
    301396    dqdt_node_t   node_copy;     // local copy of the current DQDT node
    302     uint32_t      i;             // index in the loop on children
    303     uint32_t      select;        // index of selected child
    304     xptr_t        child;         // extended pointer on a DQDT child node
    305     cxy_t         cxy;           // DQDT child node cluster identifier
    306     dqdt_node_t * ptr;           // pointer on a DQDT child node
     397    xptr_t        child_xp;      // extended pointer on a DQDT child node
     398    uint32_t      x;             // child node X coordinate
     399    uint32_t      y;             // child node Y coordinate
     400    uint32_t      select_x;      // selected child X coordinate
     401    uint32_t      select_y;      // selected child Y coordinate
    307402    uint32_t      load;          // load of the child (threads or pages)
    308403    uint32_t      load_min;      // current value of the minimal load
     
    316411    // analyse load for all children in non terminal node
    317412    load_min = 0xFFFFFFFF;
    318     select   = 0;
    319     for( i = 0 ; i < 4 ; i++ )
     413    select_x = 0;
     414    select_y = 0;
     415    for( x = 0 ; x < 2 ; x++ )
    320416    {
    321         child = node_copy.children[i];
    322         if( child != XPTR_NULL )
    323         {
    324             cxy  = (cxy_t)GET_CXY( child );
    325             ptr  = (dqdt_node_t *)GET_PTR( child );
    326             if( for_memory ) load = hal_remote_l32( XPTR( cxy , &ptr->pages ) );
    327             else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
    328             if( load < load_min )
    329             {
    330                 load_min = load;
    331                 select   = i;
     417        for( y = 0 ; y < 2 ; y++ )
     418        {
     419            child_xp = node_copy.children[x][y];
     420            if( child_xp != XPTR_NULL )
     421            {
     422                cxy_t         cxy  = GET_CXY( child_xp );
     423                dqdt_node_t * ptr  = GET_PTR( child_xp );
     424                if( for_memory ) load = hal_remote_l32( XPTR( cxy , &ptr->pages ) );
     425                else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
     426                if( load < load_min )
     427                {
     428                    load_min = load;
     429                    select_x = x;
     430                    select_y = y;
     431                }
    332432            }
    333433        }
     
    335435
    336436    // select the child with the lowest load
    337     return dqdt_select_cluster( node_copy.children[select], for_memory );
    338 }
    339 */
     437    return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory );
     438}
    340439
    341440//////////////////////////////////////////
    342441cxy_t dqdt_get_cluster_for_process( void )
    343442{
    344 
    345 return cluster_random_select();
    346 
    347 /*
    348     // build extended pointer on DQDT root node
    349         cluster_t * cluster = LOCAL_CLUSTER;
    350     uint32_t    level   = cluster->dqdt_root_level;
    351     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
    352 
    353443    // call recursive function
    354     return dqdt_select_cluster( root_xp , false );
    355 */
    356 
     444    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false );
    357445}
    358446
     
    360448cxy_t dqdt_get_cluster_for_memory( void )
    361449{
    362 
    363 return cluster_random_select();
    364  
    365 /*
    366     // build extended pointer on DQDT root node
    367         cluster_t * cluster = LOCAL_CLUSTER;
    368     uint32_t    level   = cluster->dqdt_root_level;
    369     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
    370 
    371450    // call recursive function
    372     return dqdt_select_cluster( root_xp , true );
    373 */
    374 
    375 }
    376 
     451    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true );
     452}
     453
Note: See TracChangeset for help on using the changeset viewer.