/*
 * kern/dqdt.h - Distributed Quad Decision Tree
 *
 * Author : Alain Greiner (2016,2017,2018)
 *
 * Copyright (c)  UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH
 *
 * ALMOS-kernel 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-kernel 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-kernel; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _DQDT_H_
#define _DQDT_H_

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_atomic.h>

/****************************************************************************************
 * This DQDT infrastructure maintains a topological description of ressources usage
 * in each cluster: number of threads, and number of physical pages allocated.
 *
 * - If X_SIZE or Y_SIZE are equal to 1, it makes the assumption that the cluster
 *   topology is a one dimensionnal vector, an build the smallest one-dimensionnal
 *   quad-tree covering this one-dimensionnal vector. If the number of clusters
 *   is not a power of 4, the tree is truncated as required.
 *
 *   TODO : the mapping for the one dimensionnal topology is not implemented yet [AG].
 *
 * - If both Y_SIZE and Y_SIZE are larger than 1, it makes the assumption that
 *   the clusters topology is a 2D mesh. The [X,Y] coordinates of a cluster are
 *   obtained from the CXY identifier using the Rrelevant macros.
 *      X = CXY >> Y_WIDTH   /  Y = CXY & ((1<<Y_WIDTH)-1)
 * - If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2,
 *   or the mesh contains "holes" reported in the cluster_info[x][y] array,
 *   we build the smallest two dimensionnal quad-tree covering all clusters,
 *   and this tree is truncated as required.
 * - The mesh size is supposed to contain at most 32 * 32 clusters.
 *   Therefore, it can exist at most 6 DQDT nodes in a given cluster:
 *   . Level 0 nodes exist on all clusters and have no children.
 *   . Level 1 nodes exist when both X and Y coordinates are multiple of 2
 *   . Level 2 nodes exist when both X and Y coordinates are multiple of 4
 *   . Level 3 nodes exist when both X and Y coordinates are multiple of 8
 *   . Level 4 nodes exist when both X and Y coordinates are multiple of 16
 *   . Level 5 nodes exist when both X and Y coordinates are multiple of 32
 * - For nodes other than level 0, the placement is defined as follow:
 *   . The root node is placed in the cluster containing the core executing 
 *     the dqdt_init() function.
 *   . An intermediate node (representing a given sub-tree) is placed in one
 *     cluster covered by the subtree, pseudo-randomly selected.
 ***************************************************************************************/

/****************************************************************************************
 * This structure describes a node of the DQDT.
 * The max number of children is 4, but it can be smaller for some nodes.
 * Level 0 nodes are the clusters, and have no children.
 * The root node has no parent.
 ***************************************************************************************/

typedef struct dqdt_node_s
{
	uint32_t            level;               // node level
	uint32_t            arity;               // actual children number in this node
    uint32_t            threads;             // current number of threads in subtree
    uint32_t            pages;               // current number of pages in subtree
	xptr_t              parent;              // extended pointer on parent node
	xptr_t              children[2][2];      // extended pointers on children nodes
}
dqdt_node_t;


/****************************************************************************************
 * This function recursively initializes the DQDT structure from informations
 * stored in cluster manager (x_size, y_size and cluster_info[x][y].
 * It is executed in all clusters by the local CP0, to compute level_max and register
 * the DQDT root node in each cluster manager, but only CPO in cluster 0 build actually
 * the quad-tree covering all active clusters.
 * This initialisation can use remote_accesses, because the DQDT nodes are
 * allocated as global variables in the cluster_manager, and the local addresses
 * are identical in all clusters.
 ***************************************************************************************/
void dqdt_init( void );

/****************************************************************************************
 * This local function updates the total number of threads in level 0 DQDT node,
 * and propagates the variation to the DQDT upper levels.
 * It should be called on each thread creation or destruction.
 ****************************************************************************************
 * @ increment : increment (can be positive or negative)
 ***************************************************************************************/
void dqdt_update_threads( int32_t  increment );

/****************************************************************************************
 * This local function updates the total number of pages in level 0 DQDT node,
 * and propagates the variation to the DQDT upper levels.
 * It should be called on each physical memory page allocation or release.
 ****************************************************************************************
 * @ increment : increment (can be positive or negative)
 ***************************************************************************************/
void dqdt_update_pages( int32_t increment );

/****************************************************************************************
 * This function can be called in any cluster. It traverses the DQDT tree
 * from the root to the bottom, to analyse the computing load and select the cluster
 * with the lowest number ot threads to place a new process.
 ****************************************************************************************
 * @ returns the cluster identifier with the lowest computing load.
 ***************************************************************************************/
cxy_t dqdt_get_cluster_for_process( void );

/****************************************************************************************
 * This function can be called in any cluster. It traverses the DQDT tree
 * from the root to the bottom, to analyse the memory load and select the cluster
 * with the lowest memory load for dynamic memory allocation with no locality constraint.
 ****************************************************************************************
 * @ returns the cluster identifier with the lowest memory load.
 ***************************************************************************************/
cxy_t dqdt_get_cluster_for_memory( void );

/****************************************************************************************
 * This function displays on kernel TXT0 the DQDT state for all nodes in the quad-tree.
 * It traverses the quadtree from root to bottom, and can be called by a thread 
 * running in any cluster
 ***************************************************************************************/
void dqdt_display( void );


#endif	/* _DQDT_H_ */