source: trunk/kernel/kern/dqdt.c @ 636

/*
 * dqdt.c - Distributed Quaternary Decision Tree implementation.
 *
 * Author : Alain Greiner (2016,2017,2018)
 *
 * Copyright (c)  UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-MKH is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-MKH is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_special.h>
#include <hal_macros.h>
#include <hal_atomic.h>
#include <hal_remote.h>
#include <thread.h>
#include <printk.h>
#include <chdev.h>
#include <cluster.h>
#include <bits.h>
#include <dqdt.h>


///////////////////////////////////////////////////////////////////////////////////////////
//      Extern variables
///////////////////////////////////////////////////////////////////////////////////////////

extern chdev_directory_t  chdev_dir;  // defined in chdev.h / allocated in kernel_init.c

///////////////////////////////////////////////////////////////////////////////////////////
// This static recursive function traverse the DQDT quad-tree from root to bottom.
///////////////////////////////////////////////////////////////////////////////////////////
static void dqdt_recursive_print( xptr_t  node_xp )
{
        uint32_t x;
        uint32_t y;
    dqdt_node_t node;

    // get node local copy
    hal_remote_memcpy( XPTR( local_cxy , &node ), node_xp , sizeof(dqdt_node_t) );

    // display node content
        nolock_printk("- level %d / cluster %x : threads = %x / pages = %x / clusters %d / cores %d\n",
    node.level, GET_CXY( node_xp ), node.threads, node.pages, node.clusters, node.cores );

    // recursive call on children if node is not terminal
    if ( node.level > 0 )
    {
        for ( x = 0 ; x < 2 ; x++ )
        {
            for ( y = 0 ; y < 2 ; y++ )
            {
                xptr_t iter_xp = node.children[x][y];
                if ( iter_xp != XPTR_NULL ) dqdt_recursive_print( iter_xp );
            }
        }
    }
}

/////////////////////////
void dqdt_display( void )
{
    // get extended pointer on DQDT root node
        cluster_t * cluster = &cluster_manager;
    xptr_t      root_xp = cluster->dqdt_root_xp;

    // get pointers on TXT0 chdev
    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
    chdev_t * txt0_ptr = GET_PTR( txt0_xp );

    // get extended pointer on remote TXT0 lock
    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );

    // get TXT0 lock
    remote_busylock_acquire( lock_xp );

    // print header
    nolock_printk("\n***** DQDT state\n\n");

    // call recursive function
    dqdt_recursive_print( root_xp );

    // release TXT0 lock
    remote_busylock_release( lock_xp );
}

///////////////////////////////////////////////////////////////////////////////////////
// This static function initializes recursively, from top to bottom, the quad-tree
// infrastructure. The DQDT nodes are allocated as global variables in each local
// cluster manager. At each level in the quad-tree, this function initializes the
// node identified by the <cxy> and <level> arguments, selects in each child 
// macro-cluster the precise cluster where will be placed the subtree root node, 
// and call recursively itself to initialize the child node in the selected cluster.
///////////////////////////////////////////////////////////////////////////////////////
// @ node cxy  : cluster containing the node to initialize
// @ level     : level of node to be initialised
// @ parent_xp : extended pointer on the parent node
///////////////////////////////////////////////////////////////////////////////////////
static void dqdt_recursive_build( cxy_t    node_cxy,
                                  uint32_t level,
                                  xptr_t   parent_xp )
{
    assert( (level < 5) , __FUNCTION__, "illegal DQDT level %d\n", level );
  
    uint32_t node_x;         // node X coordinate
    uint32_t node_y;         // node Y coordinate
    uint32_t mask;           // to compute associated macro-cluster coordinates
    uint32_t node_base_x;    // associated macro_cluster X coordinate
    uint32_t node_base_y;    // associated macro_cluster y coordinate
    uint32_t half;           // associated macro-cluster half size
    uint32_t cores;          // number of cores in macro cluster
    uint32_t clusters;       // number of clusters in macro cluster

    // get node cluster coordinates
    node_x = HAL_X_FROM_CXY( node_cxy );
    node_y = HAL_Y_FROM_CXY( node_cxy );
        
    // get macro-cluster mask and half-size
    mask   = (1 << level) - 1;
    half   = (level > 0) ? (1 << (level - 1)) : 0;

    // get macro-cluster coordinates 
    node_base_x = node_x & ~mask;
    node_base_y = node_y & ~mask;

    // get pointer on local cluster manager
    cluster_t * cluster = LOCAL_CLUSTER;

    // build local and extended pointer on node to be initialized
    dqdt_node_t * node_ptr = &cluster->dqdt_tbl[level];
    xptr_t        node_xp  = XPTR( node_cxy , node_ptr );

#if DEBUG_DQDT_INIT
printk("\n[DBG] %s : cxy(%d,%d) / level %d / mask %x / half %d / ptr %x\n",
__FUNCTION__, node_x, node_y, level, mask, half, node_ptr );
#endif
  
    // make remote node default initialisation
    hal_remote_memset( node_xp , 0 , sizeof( dqdt_node_t ) );

    // initialize <parent> field
    hal_remote_s64( XPTR( node_cxy , &node_ptr->parent ) , parent_xp );

    // initialize <level> field
    hal_remote_s32( XPTR( node_cxy , &node_ptr->level ) , level );

    // recursive initialisation 
    if( level == 0 )                      // terminal case : cluster
    {
        // initialize <clusters> field in node
        hal_remote_s32( XPTR( node_cxy , &node_ptr->clusters ) , 1 );

        // initialize <cores> field in node
        cores = hal_remote_l32( XPTR ( node_cxy , &cluster->cores_nr ) );
        hal_remote_s32( XPTR( node_cxy , &node_ptr->cores ) , cores );
    }
    else                                  // non terminal : macro-cluster
    {
        bool_t        found;
        uint32_t      x;
        uint32_t      y;
        cxy_t         child_cxy;
        xptr_t        child_xp;
        dqdt_node_t * child_ptr =  &cluster->dqdt_tbl[level-1];

        // search an active cluster in child[0][0] macro-cluster
        found = false; 
        for( x = node_base_x ; 
        (x < (node_base_x + half)) && (found == false) ; x++ )
        {
            for( y = node_base_y ; 
            (y < (node_base_y + half)) && (found == false) ; y++ )
            {
                child_cxy = HAL_CXY_FROM_XY( x , y );

                if( cluster_is_active( child_cxy ) )
                {
                    // initialize recursively selected child[0][0] node
                    dqdt_recursive_build( child_cxy , level-1 , node_xp );

                    // build extended pointer on child[0][0] node
                    child_xp = XPTR( child_cxy , child_ptr );

                    // update <cores> field in node
                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );

                    // update <clusters> field in node
                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );

                    // update <child[0][0]> field in node
                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][0] ), child_xp );

                    // udate <arity> field in node
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
   
                    // exit loops
                    found = true;
                }
            }
        }

        // search an active cluster in child[0][1] macro-cluster
        found = false; 
        for( x = node_base_x ; 
        (x < (node_base_x + half)) && (found == false) ; x++ )
        {
            for( y = (node_base_y + half) ; 
            (y < (node_base_y + (half<<1))) && (found == false) ; y++ )
            {
                child_cxy = HAL_CXY_FROM_XY( x , y );

                if( cluster_is_active( child_cxy ) )
                {
                    // initialize recursively selected child[0][1] node
                    dqdt_recursive_build( child_cxy , level-1 , node_xp );

                    // build extended pointer on child[0][1] node
                    child_xp = XPTR( child_cxy , child_ptr );

                    // update <cores> field in node
                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );

                    // update <clusters> field in node
                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );

                    // update <child[0][1]> field in node
                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][1] ), child_xp );

                    // udate <arity> field in node
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
   
                    // exit loops
                    found = true;
                }
            }
        }

        // search an active cluster in child[1][0] macro-cluster
        found = false; 
        for( x = (node_base_x +half) ; 
        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
        {
            for( y = node_base_y ; 
            (y < (node_base_y + half)) && (found == false) ; y++ )
            {
                child_cxy = HAL_CXY_FROM_XY( x , y );

                if( cluster_is_active( child_cxy ) )
                {
                    // initialize recursively selected child[1][0] node
                    dqdt_recursive_build( child_cxy , level-1 , node_xp );

                    // build extended pointer on child[1][0] node
                    child_xp = XPTR( child_cxy , child_ptr );

                    // update <cores> field in node
                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );

                    // update <clusters> field in node
                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );

                    // update <child[1][0]> field in node
                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][0] ), child_xp );

                    // udate <arity> field in node
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
   
                    // exit loops
                    found = true;
                }
            }
        }

        // search an active cluster in child[1][1] macro-cluster
        found = false; 
        for( x = (node_base_x + half) ; 
        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
        {
            for( y = (node_base_y + half) ; 
            (y < (node_base_y + (half<<1))) && (found == false) ; y++ )
            {
                child_cxy = HAL_CXY_FROM_XY( x , y );

                if( cluster_is_active( child_cxy ) )
                {
                    // initialize recursively selected child[1][1] node
                    dqdt_recursive_build( child_cxy , level-1 , node_xp );

                    // build extended pointer on child[1][1] node
                    child_xp = XPTR( child_cxy , child_ptr );

                    // update <cores> field in node
                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );

                    // update <clusters> field in node
                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );

                    // update <child[1][1]> field in node
                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][1] ), child_xp );

                    // udate <arity> field in node
                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
   
                    // exit loops
                    found = true;
                }
            }
        }
    }
}  // end dqdt_recursive_build()

//////////////////////
void dqdt_init( void )
{
    // get x_size & y_size from cluster manager
    cluster_t * cluster = &cluster_manager;
    uint32_t    x_size  = cluster->x_size;
    uint32_t    y_size  = cluster->y_size;

    assert( ((x_size <= 16) && (y_size <= 16)) , "illegal mesh size\n");
 
    // compute level_max
    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
    uint32_t  y_size_ext = POW2_ROUNDUP( y_size );
    uint32_t  size_ext   = MAX( x_size_ext , y_size_ext );
    uint32_t  level_max  = bits_log2( size_ext );

    // each CP0 register the DQDT root in local cluster manager
    cluster->dqdt_root_xp = XPTR( 0 , &cluster->dqdt_tbl[level_max] );

#if DEBUG_DQDT_INIT
if( local_cxy == 0 )
printk("\n[DBG] %s : x_size = %d / y_size = %d / level_max = %d\n",
__FUNCTION__, x_size, y_size, level_max );
#endif
    
    // only CP0 in cluster 0 call the recursive function to build the quad-tree
    if (local_cxy == 0) dqdt_recursive_build( local_cxy , level_max , XPTR_NULL );

#if DEBUG_DQDT_INIT
if( local_cxy == 0 ) dqdt_display();
#endif

}  // end dqdt_init()


///////////////////////////////////////////////////////////////////////////
// This recursive function is called by both the dqdt_increment_pages()
// and by the dqdt_decrement_pages() functions.
// It traverses the quad tree from clusters to root.
///////////////////////////////////////////////////////////////////////////
// @ node_xp    : extended pointer on current node
// @ increment  : number of pages variation
///////////////////////////////////////////////////////////////////////////
static void dqdt_propagate_pages( xptr_t  node_xp,
                                  int32_t increment )
{
    // get current node cluster identifier and local pointer
    cxy_t         node_cxy = GET_CXY( node_xp );
    dqdt_node_t * node_ptr = GET_PTR( node_xp );

    // update current node pages number
    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->pages ) , increment );

    // get extended pointer on parent node
    xptr_t parent_xp = (xptr_t)hal_remote_l64( XPTR( node_cxy , &node_ptr->parent ) );

    // propagate if required
    if ( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp, increment );
}

////////////////////////////////////////
void dqdt_increment_pages( cxy_t    cxy,
                           uint32_t order )
{
    // get local pointer on node[0] (same in all clusters)
    dqdt_node_t * node_ptr = &LOCAL_CLUSTER->dqdt_tbl[0];

    // update DQDT node[0] in remote cluster cxy
    hal_remote_atomic_add( XPTR( cxy , &node_ptr->pages ) , (1 << order) );

    // get extended pointer on parent node in remote cluster cxy
    xptr_t parent_xp = hal_remote_l64( XPTR( cxy , &node_ptr->parent ) );

     // propagate to DQDT upper levels
    if( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp , (1 << order) );

#if DEBUG_DQDT_UPDATE_PAGES
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_UPDATE_PAGES )
printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid,
hal_remote_l32( XPTR( cxy , &node_ptr->pages ), cxy, cycle );
#endif

}

////////////////////////////////////////
void dqdt_decrement_pages( cxy_t    cxy,
                           uint32_t order )
{
    // get local pointer on node[0] (same in all clusters)
    dqdt_node_t * node_ptr = &LOCAL_CLUSTER->dqdt_tbl[0];

    // update DQDT node[0] in remote cluster cxy
    hal_remote_atomic_add( XPTR( cxy , &node_ptr->pages ) , -(1 << order) );

    // get extended pointer on parent node in remote cluster cxy
    xptr_t parent_xp = hal_remote_l64( XPTR( cxy , &node_ptr->parent ) );

     // propagate to DQDT upper levels
    if( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp , -(1 << order) );

#if DEBUG_DQDT_UPDATE_PAGES
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_UPDATE_PAGES )
printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid,
hal_remote_l32( XPTR( cxy , &node_ptr->pages ), cxy, cycle );
#endif

}



///////////////////////////////////////////////////////////////////////////
// This recursive function is called by both the dqdt_increment_threads() 
// and by the dqdt_decrement_threads functions.
// It traverses the quad tree from clusters to root.
///////////////////////////////////////////////////////////////////////////
// @ node       : extended pointer on current node
// @ increment  : number of pages variation
///////////////////////////////////////////////////////////////////////////
static void dqdt_propagate_threads( xptr_t  node,
                                    int32_t increment )
{
    // get current node cluster identifier and local pointer
    cxy_t         cxy = GET_CXY( node );
    dqdt_node_t * ptr = GET_PTR( node );

    // update current node threads number
    hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , increment );

    // get extended pointer on parent node
    xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) );

    // propagate if required
    if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
}

///////////////////////////////////
void dqdt_increment_threads( void )
{
        cluster_t   * cluster = LOCAL_CLUSTER;
    dqdt_node_t * node    = &cluster->dqdt_tbl[0];

    // update DQDT node level 0
    hal_atomic_add( &node->threads , 1 );

    // propagate to DQDT upper levels
    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , 1 );

#if DEBUG_DQDT_UPDATE_THREADS
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_UPDATE_THREADS )
printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, 
node->threads, local_cxy, cycle );
#endif

}

///////////////////////////////////
void dqdt_decrement_threads( void )
{
        cluster_t   * cluster = LOCAL_CLUSTER;
    dqdt_node_t * node    = &cluster->dqdt_tbl[0];

    // update DQDT node level 0
    hal_atomic_add( &node->threads , -1 );

    // propagate to DQDT upper levels
    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , -1 );

#if DEBUG_DQDT_UPDATE_THREADS
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_UPDATE_THREADS )
printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, 
node->threads, local_cxy, cycle );
#endif

}


/////////////////////////////////////////////////////////////////////////////////////
// This recursive function is called by both the dqdt_get_cluster_for_process()
// and by the dqdt_get_cluster_for_memory() functions to select the cluster with the 
// smallest number of threads per core, or the smallest number of pages per cluster.
// It traverses the quad tree from root to clusters.
/////////////////////////////////////////////////////////////////////////////////////
static cxy_t dqdt_select_cluster( xptr_t node,
                                  bool_t for_memory )
{
    dqdt_node_t   node_copy;     // local copy of the current DQDT node
    xptr_t        child_xp;      // extended pointer on a DQDT child node
    uint32_t      x;             // child node X coordinate 
    uint32_t      y;             // child node Y coordinate
    uint32_t      select_x;      // selected child X coordinate
    uint32_t      select_y;      // selected child Y coordinate
    uint32_t      load;          // load of the child (threads or pages)
    uint32_t      load_min;      // current value of the minimal load

    // get DQDT node local copy
    hal_remote_memcpy( XPTR( local_cxy , &node_copy ), node , sizeof(dqdt_node_t) );

    // return cluster identifier for a terminal mode
    if( node_copy.level == 0 ) return GET_CXY(node);

    // analyse load for all children in non terminal node
    load_min = 0xFFFFFFFF;
    select_x = 0;
    select_y = 0;
    for( x = 0 ; x < 2 ; x++ )
    {
        for( y = 0 ; y < 2 ; y++ )
        {
            child_xp = node_copy.children[x][y];
            if( child_xp != XPTR_NULL )
            {
                cxy_t         cxy  = GET_CXY( child_xp );
                dqdt_node_t * ptr  = GET_PTR( child_xp );

                // compute average load  for each child
                if( for_memory )
                {
                    load = hal_remote_l32( XPTR( cxy , &ptr->pages ) ) /
                           hal_remote_l32( XPTR( cxy , &ptr->clusters ) );
                }
                else
                {
                    load = hal_remote_l32( XPTR( cxy , &ptr->threads ) ) /
                           hal_remote_l32( XPTR( cxy , &ptr->cores ) );
                }

                // select children with smallest load
                if( load <= load_min )
                {
                    load_min = load;
                    select_x = x;
                    select_y = y;
                }
            }
        }
    }

    // select the child with the lowest load
    return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory );

}  // end dqdt_select_cluster()


//////////////////////////////////////////
cxy_t dqdt_get_cluster_for_process( void )
{
    // call recursive function
    cxy_t cxy = dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false );

#if DEBUG_DQDT_SELECT_FOR_PROCESS
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_SELECT_FOR_PROCESS )
printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle );
#endif

    return cxy;
}

/////////////////////////////////////////
cxy_t dqdt_get_cluster_for_memory( void )
{
    // call recursive function
    cxy_t cxy = dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true );

#if DEBUG_DQDT_SELECT_FOR_MEMORY
uint32_t cycle = hal_get_cycles();
if( cycle > DEBUG_DQDT_SELECT_FOR_MEMORY )
printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n",
__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle );
#endif

    return cxy;
}