Changeset 582 for trunk/kernel/kern/dqdt.c
- Timestamp:
- Oct 11, 2018, 5:04:28 PM (6 years ago)
- File:
-
- 1 edited
-
trunk/kernel/kern/dqdt.c (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/kern/dqdt.c
r564 r582 25 25 #include <hal_kernel_types.h> 26 26 #include <hal_special.h> 27 #include <hal_macros.h> 27 28 #include <hal_atomic.h> 28 29 #include <hal_remote.h> … … 40 41 extern chdev_directory_t chdev_dir; // defined in chdev.h / allocated in kernel_init.c 41 42 42 /*43 43 /////////////////////////////////////////////////////////////////////////////////////////// 44 44 // This static recursive function traverse the DQDT quad-tree from root to bottom. … … 46 46 static void dqdt_recursive_print( xptr_t node_xp ) 47 47 { 48 uint32_t i; 48 uint32_t x; 49 uint32_t y; 49 50 dqdt_node_t node; 50 51 … … 59 60 if ( node.level > 0 ) 60 61 { 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 } 64 69 } 65 70 } 66 71 } 67 */68 72 69 73 ///////////////////////// 70 74 void dqdt_display( void ) 71 75 { 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; 79 79 80 80 // get pointers on TXT0 chdev … … 95 95 dqdt_recursive_print( root_xp ); 96 96 97 // release lock97 // release TXT0 lock 98 98 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 /////////////////////////////////////////////////////////////////////////////////////// 114 static 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 146 printk("\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 ////////////////////// 280 void 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"); 108 288 109 289 // compute level_max 110 290 uint32_t x_size_ext = POW2_ROUNDUP( x_size ); 111 291 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 299 if( local_cxy == 0 ) 300 printk("\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 308 if( local_cxy == 0 ) dqdt_display(); 309 #endif 310 311 } // end dqdt_init() 312 202 313 /////////////////////////////////////////////////////////////////////////// 203 314 // This recursive function is called by the dqdt_update_threads() function. … … 223 334 if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment ); 224 335 } 225 */ 226 227 /* 336 228 337 /////////////////////////////////////////////////////////////////////////// 229 338 // This recursive function is called by the dqdt_update_pages() function. … … 249 358 if ( parent != XPTR_NULL ) dqdt_propagate_pages( parent, increment ); 250 359 } 251 */252 360 253 361 ///////////////////////////////////////////// 254 void dqdt_update_threads( int32_t increment __attribute__ ((__unused__)) ) 255 { 256 257 return; 258 259 /* 362 void dqdt_update_threads( int32_t increment ) 363 { 260 364 cluster_t * cluster = LOCAL_CLUSTER; 261 365 dqdt_node_t * node = &cluster->dqdt_tbl[0]; … … 266 370 // propagate to DQDT upper levels 267 371 if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment ); 268 */269 270 372 } 271 373 272 374 /////////////////////////////////////////// 273 void dqdt_update_pages( int32_t increment __attribute__ ((__unused__)) ) 274 { 275 276 return; 277 278 /* 375 void dqdt_update_pages( int32_t increment ) 376 { 279 377 cluster_t * cluster = LOCAL_CLUSTER; 280 378 dqdt_node_t * node = &cluster->dqdt_tbl[0]; … … 285 383 // propagate to DQDT upper levels 286 384 if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment ); 287 */ 288 289 } 290 291 /* 385 } 386 292 387 //////////////////////////////////////////////////////////////////////////////// 293 388 // This recursive function is called by both the dqdt_get_cluster_for_process() … … 300 395 { 301 396 dqdt_node_t node_copy; // local copy of the current DQDT node 302 uint32_t i; // index in the loop on children303 uint32_t select; // index of selected child304 xptr_t child; // extended pointer on a DQDT child node305 cxy_t cxy; // DQDT child node cluster identifier306 dqdt_node_t * ptr; // pointer on a DQDT child node397 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 307 402 uint32_t load; // load of the child (threads or pages) 308 403 uint32_t load_min; // current value of the minimal load … … 316 411 // analyse load for all children in non terminal node 317 412 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++ ) 320 416 { 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 } 332 432 } 333 433 } … … 335 435 336 436 // 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 } 340 439 341 440 ////////////////////////////////////////// 342 441 cxy_t dqdt_get_cluster_for_process( void ) 343 442 { 344 345 return cluster_random_select();346 347 /*348 // build extended pointer on DQDT root node349 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 353 443 // call recursive function 354 return dqdt_select_cluster( root_xp , false ); 355 */ 356 444 return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false ); 357 445 } 358 446 … … 360 448 cxy_t dqdt_get_cluster_for_memory( void ) 361 449 { 362 363 return cluster_random_select();364 365 /*366 // build extended pointer on DQDT root node367 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 371 450 // 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.
