Index: trunk/kernel/kern/dqdt.c
===================================================================
--- trunk/kernel/kern/dqdt.c	(revision 564)
+++ trunk/kernel/kern/dqdt.c	(revision 582)
@@ -25,4 +25,5 @@
 #include <hal_kernel_types.h>
 #include <hal_special.h>
+#include <hal_macros.h>
 #include <hal_atomic.h>
 #include <hal_remote.h>
@@ -40,5 +41,4 @@
 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.
@@ -46,5 +46,6 @@
 static void dqdt_recursive_print( xptr_t  node_xp )
 {
-	uint32_t i;
+	uint32_t x;
+	uint32_t y;
     dqdt_node_t node;
 
@@ -59,22 +60,21 @@
     if ( node.level > 0 )
     {
-        for ( i = 0 ; i < 4 ; i++ )
-        {
-            if ( node.children[i] != XPTR_NULL ) dqdt_recursive_print( node.children[i] );
+        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 )
 {
-    return;
-
-/*
-    // 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 extended pointer on DQDT root node
+	cluster_t * cluster = &cluster_manager;
+    xptr_t      root_xp = cluster->dqdt_root_xp;
 
     // get pointers on TXT0 chdev
@@ -95,109 +95,220 @@
     dqdt_recursive_print( root_xp );
 
-    // release lock
+    // release TXT0 lock
     remote_busylock_release( lock_xp );
-*/
-
-}
-
-////////////////////////////////////
-uint32_t dqdt_init( uint32_t x_size,
-                    uint32_t y_size )
-{
-    assert( ((x_size <= 32) && (y_size <= 32)) , "illegal mesh size\n");
+}
+
+///////////////////////////////////////////////////////////////////////////////////////
+// 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
+// parent DQDT node in the cluster identified by the <cxy> and <level> arguments.
+// A each level, it selects in each child macro-cluster the precise cluster where 
+// will be placed the the subtree root node, and call recursively itself to
+// initialize the child node in this 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
+
+    // get remote 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;
+
+    // get local pointer on remote node to be initialized
+    dqdt_node_t * node  = &cluster->dqdt_tbl[level];
+
+#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 );
+#endif
+  
+    // make remote node default initialisation
+    hal_remote_memset( XPTR( node_cxy , node ) , 0 , sizeof( dqdt_node_t ) );
+
+    // recursive initialisation 
+    if( level == 0 )                      // terminal case
+    {
+        // update parent field
+        hal_remote_s64( XPTR( node_cxy , &node->parent ) , parent_xp );
+    }
+    else                                  // non terminal
+    {
+        uint32_t x;
+        uint32_t y;
+        cxy_t    cxy;
+        bool_t   found;
+
+        // update <level> in remote node
+        hal_remote_s32( XPTR( node_cxy , &node->level ) , level );
+
+        // try to find a valid 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++ )
+            {
+                cxy = HAL_CXY_FROM_XY( x , y );
+                if( cluster_is_active( cxy ) )
+                {
+                    // update <child[0][0]> in remote inode
+                    hal_remote_s64( XPTR( node_cxy , &node->children[0][0] ), 
+                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
+
+                    // udate <arity> in remote node
+                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
+
+                    // initialize recursively child[0][0] node
+                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
+   
+                    // exit loops
+                    found = true;
+                }
+            }
+        }
+
+        // try to find a valid 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<<2))) && (found == false) ; y++ )
+            {
+                cxy = HAL_CXY_FROM_XY( x , y );
+                if( cluster_is_active( cxy ) )
+                {
+                    // update <child[0][1]> in remote inode
+                    hal_remote_s64( XPTR( node_cxy , &node->children[0][1] ), 
+                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
+
+                    // udate <arity> in remote node
+                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
+
+                    // initialize recursively child[0][1] node
+                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
+   
+                    // exit loops
+                    found = true;
+                }
+            }
+        }
+            
+        // try to find a valid 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++ )
+            {
+                cxy = HAL_CXY_FROM_XY( x , y );
+                if( cluster_is_active( cxy ) )
+                {
+                    // update <child[1][0]> in remote inode
+                    hal_remote_s64( XPTR( node_cxy , &node->children[1][0] ), 
+                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
+
+                    // udate <arity> in remote node
+                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
+
+                    // initialize recursively child[1][0] node
+                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
+   
+                    // exit loops
+                    found = true;
+                }
+            }
+        }
+
+        // try to find a valid 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<<2))) && (found == false) ; y++ )
+            {
+                cxy = HAL_CXY_FROM_XY( x , y );
+                if( cluster_is_active( cxy ) )
+                {
+                    // update <child[1][1]> in remote inode
+                    hal_remote_s64( XPTR( node_cxy , &node->children[1][1] ), 
+                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
+
+                    // udate <arity> in remote node
+                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
+
+                    // initialize recursively child[1][1] node
+                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
+   
+                    // 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 * size_ext) >> 1) + 1;
-
-return level_max;
-
-/*
-	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_t   * cluster = LOCAL_CLUSTER;
-
-    // get cluster coordinates
-    uint32_t    x       = HAL_X_FROM_CXY( local_cxy );
-    uint32_t    y       = HAL_Y_FROM_CXY( local_cxy );
-
-    // 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 = HAL_CXY_FROM_XY( (x & ~pmask) , (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 + HAL_CXY_FROM_XY( 0 , (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 + HAL_CXY_FROM_XY( (1<<(level-1)) , 0 );
-                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 + HAL_CXY_FROM_XY( (1<<(level-1)) , (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()
-
-/*
+    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 the dqdt_update_threads() function.
@@ -223,7 +334,5 @@
     if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
 }
-*/
-
-/*
+
 ///////////////////////////////////////////////////////////////////////////
 // This recursive function is called by the dqdt_update_pages() function.
@@ -249,13 +358,8 @@
     if ( parent != XPTR_NULL ) dqdt_propagate_pages( parent, increment );
 }
-*/
 
 /////////////////////////////////////////////
-void dqdt_update_threads( int32_t increment __attribute__ ((__unused__)) )
-{
-
-return;
-
-/*
+void dqdt_update_threads( int32_t increment )
+{
 	cluster_t   * cluster = LOCAL_CLUSTER;
     dqdt_node_t * node    = &cluster->dqdt_tbl[0];
@@ -266,15 +370,9 @@
     // propagate to DQDT upper levels
     if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment );
-*/
-
 }
 
 ///////////////////////////////////////////
-void dqdt_update_pages( int32_t increment  __attribute__ ((__unused__)) )
-{
-
-return;
-
-/*
+void dqdt_update_pages( int32_t increment )
+{
 	cluster_t   * cluster = LOCAL_CLUSTER;
     dqdt_node_t * node    = &cluster->dqdt_tbl[0];
@@ -285,9 +383,6 @@
     // 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()
@@ -300,9 +395,9 @@
 {
     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
+    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
@@ -316,18 +411,23 @@
     // analyse load for all children in non terminal node
     load_min = 0xFFFFFFFF;
-    select   = 0;
-    for( i = 0 ; i < 4 ; i++ )
+    select_x = 0;
+    select_y = 0;
+    for( x = 0 ; x < 2 ; x++ )
     {
-        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_l32( XPTR( cxy , &ptr->pages ) );
-            else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
-            if( load < load_min )
-            {
-                load_min = load;
-                select   = i;
+        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 );
+                if( for_memory ) load = hal_remote_l32( XPTR( cxy , &ptr->pages ) );
+                else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
+                if( load < load_min )
+                {
+                    load_min = load;
+                    select_x = x;
+                    select_y = y;
+                }
             }
         }
@@ -335,24 +435,12 @@
 
     // select the child with the lowest load
-    return dqdt_select_cluster( node_copy.children[select], for_memory );
-}
-*/
+    return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory );
+}
 
 //////////////////////////////////////////
 cxy_t dqdt_get_cluster_for_process( void )
 {
-
-return cluster_random_select();
-
-/*
-    // 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 );
-*/
-
+    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false );
 }
 
@@ -360,17 +448,6 @@
 cxy_t dqdt_get_cluster_for_memory( void )
 {
-
-return cluster_random_select();
- 
-/*
-    // 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 );
-*/
-
-}
-
+    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true );
+}
+
