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

/*
 * 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_types.h>
#include <hal_special.h>
#include <hal_atomic.h>
#include <hal_remote.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 i;
    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 in cluster %x (node %x) : threads = %x / pages = %x\n",
    node.level, GET_CXY( node_xp ), GET_PTR( node_xp ), node.threads, node.pages );

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

///////////////////
void dqdt_display()
{
    reg_t   save_sr;

    // build extended pointer on DQDT root node
        cluster_t * cluster = LOCAL_CLUSTER;
    uint32_t    level   = cluster->dqdt_root_level;
    xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );

    // 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 chdev lock
    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );

    // get TXT0 lock in busy waiting mode
    remote_spinlock_lock_busy( lock_xp , &save_sr );

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

    // call recursive function
    dqdt_recursive_print( root_xp );

    // release lock
    remote_spinlock_unlock_busy( lock_xp , save_sr );
}

////////////////////////////////////
uint32_t dqdt_init( uint32_t x_size,
                    uint32_t y_size,
                    uint32_t y_width )
{
    assert( ((x_size <= 32) && (y_size <= 32)) , __FUNCTION__ , "illegal mesh size\n");

        dqdt_node_t * node;
    cxy_t         p_cxy;         // cluster coordinates for parent node
    cxy_t         c_cxy;         // cluster coordinates for child node
    uint32_t      level;         // node level in quad tree
    uint32_t      mask;          // mask on node coordinates to compute existence condition
    uint32_t      pmask;         // mask to compute parent coordinates from child coordinates
    cluster_t   * cluster;       // pointer on local cluster

    cluster = LOCAL_CLUSTER;

    // 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 * size_ext) >> 1) + 1;

    // get cluster coordinates
    uint32_t    x       = local_cxy >> y_width;
    uint32_t    y       = local_cxy & ((1<<y_width)-1);

    // loop on local dqdt nodes (at most one node per level)
    for( level = 0 ; level < level_max ; level++ )
    {
        // get pointer on the node to be initialised
        node = &cluster->dqdt_tbl[level];

        // set default values
        node->level       = level;
        node->arity       = 0;
        node->threads     = 0;
        node->pages       = 0;
        node->parent      = XPTR_NULL;
        node->children[0] = XPTR_NULL;
        node->children[1] = XPTR_NULL;
        node->children[2] = XPTR_NULL;
        node->children[3] = XPTR_NULL;

        // compute masks depending on level : 0x1, 0x3, 0x7, 0xF, 0x1F etc.
        mask  = (1<<level)-1;
        pmask = (1<<(level+1))-1;

        // check the node  existence condition at each level
        if( ((x & mask) == 0) && ((y & mask) == 0) )
        {
            // set parent extended pointer
            p_cxy = ((x & ~pmask)<<y_width) + (y & ~pmask);
            node->parent = XPTR( p_cxy , &cluster->dqdt_tbl[level+1] );

            // set child[0] extended pointer (same [x,y] coordinates)
            if ( level > 0 )
            {
                c_cxy = local_cxy;
                node->children[0] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
                node->arity++;
            }

            // set child[1] extended pointer (coordinates may overflow)
            if ( (level > 0) && ((y + (1<<(level-1))) < y_size) )
            {
                c_cxy = local_cxy + (1<<(level-1));
                node->children[1] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1] );
                node->arity++;
            }

            // set child[2] extended pointer (coordinates may overflow)
            if ( (level > 0) && ((x + (1<<(level-1))) < x_size) )
            {
                c_cxy = local_cxy + ((1<<(level-1))<<y_width);
                node->children[2] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
                node->arity++;
            }

            // set child[3] extended pointer (coordinates may overflow)
            if ( (level > 0) && 
                 ((x + (1<<(level-1))) < x_size) && 
                 ((y + (1<<(level-1))) < y_size) )
            {
                c_cxy = local_cxy + ((1<<(level-1))<<y_width) + (1<<(level-1));
                node->children[3] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
                node->arity++;
            }
        }  // end if existence condition
    }  // end for level

    return level_max;

} // end dqdt_init()

///////////////////////////////////////////////////////////////////////////
// This recursive function is called by the dqdt_update_threads() function.
// It traverses the quad tree from clusters to root.
///////////////////////////////////////////////////////////////////////////
// @ node       : extended pointer on current node
// @ increment  : number of threads 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_lwd( XPTR( cxy , &ptr->parent ) );

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

///////////////////////////////////////////////////////////////////////////
// This recursive function is called by the dqdt_update_pages() function.
// It traverses the quad tree from clusters to root.
///////////////////////////////////////////////////////////////////////////
// @ node       : extended pointer on current node
// @ increment  : number of pages variation
///////////////////////////////////////////////////////////////////////////
static void dqdt_propagate_pages( 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->pages ) , increment );

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

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

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

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

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

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

    // update DQDT node level 0
    hal_atomic_add( &node->pages , increment );

    // propagate to DQDT upper levels
    if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment );
}


////////////////////////////////////////////////////////////////////////////////
// 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 smallest number of thread, or smallest number of allocated pages.
// 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
    uint32_t      i;             // index in the loop on children
    uint32_t      select;        // index of selected child
    xptr_t        child;         // extended pointer on a DQDT child node
    cxy_t         cxy;           // DQDT child node cluster identifier
    dqdt_node_t * ptr;           // pointer on a DQDT child node
    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   = 0;
    for( i = 0 ; i < 4 ; i++ )
    {
        child = node_copy.children[i];
        if( child != XPTR_NULL )
        {
            cxy  = (cxy_t)GET_CXY( child );
            ptr  = (dqdt_node_t *)GET_PTR( child );
            if( for_memory ) load = hal_remote_lw( XPTR( cxy , &ptr->pages ) );
            else             load = hal_remote_lw( XPTR( cxy , &ptr->threads ) );
            if( load < load_min )
            {
                load_min = load;
                select   = i;
            }
        }
    }

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

////////////////////////////////////
cxy_t dqdt_get_cluster_for_process()
{
    // build extended pointer on DQDT root node
        cluster_t * cluster = LOCAL_CLUSTER;
    uint32_t    level   = cluster->dqdt_root_level;
    xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );

    // call recursive function
    return dqdt_select_cluster( root_xp , false );
}

////////////////////////////////////
cxy_t dqdt_get_cluster_for_memory()
{
    // build extended pointer on DQDT root node
        cluster_t * cluster = LOCAL_CLUSTER;
    uint32_t    level   = cluster->dqdt_root_level;
    xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );

    // call recursive function
    return dqdt_select_cluster( root_xp , true );
}