Changeset 635 for trunk/kernel/libk/grdxt.c
- Timestamp:
- Jun 26, 2019, 11:42:37 AM (5 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/libk/grdxt.c
r626 r635 30 30 #include <grdxt.h> 31 31 32 //////////////////////////////////////////////////////////////////////////////////////// 33 // Local access functions 34 //////////////////////////////////////////////////////////////////////////////////////// 35 32 36 ///////////////////////////////// 33 37 error_t grdxt_init( grdxt_t * rt, … … 44 48 45 49 // allocates first level array 46 req.type = KMEM_ GENERIC;47 req. size = sizeof(void *) << ix1_width;50 req.type = KMEM_KCM; 51 req.order = ix1_width + ( (sizeof(void*) == 4) ? 2 : 3 ); 48 52 req.flags = AF_KERNEL | AF_ZERO; 49 53 root = kmem_alloc( &req ); 50 if( root == NULL ) return ENOMEM; 54 55 if( root == NULL ) 56 { 57 printk("\n[ERROR] in %s : cannot allocate first level array\n", __FUNCTION__); 58 return -1; 59 } 51 60 52 61 rt->root = root; … … 71 80 uint32_t ix1; 72 81 uint32_t ix2; 73 74 // check rt 82 uint32_t ix3; 83 75 84 assert( (rt != NULL) , "pointer on radix tree is NULL\n" ); 76 77 req.type = KMEM_GENERIC;78 85 79 86 for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ ) … … 89 96 if( ptr3 == NULL ) continue; 90 97 98 for( ix3=0 ; ix3 < (uint32_t)(1 << w3) ; ix3++ ) 99 { 100 if( ptr3[ix3] != NULL ) 101 { 102 printk("\n[WARNING] in %s : ptr3[%d][%d][%d] non empty\n", 103 __FUNCTION__, ix1, ix2, ix3 ); 104 } 105 } 106 91 107 // release level 3 array 108 req.type = KMEM_KCM; 92 109 req.ptr = ptr3; 93 req.type = KMEM_GENERIC;94 req.size = sizeof(void *) * (1 << w3);95 110 kmem_free( &req ); 96 111 } 97 112 98 113 // release level 2 array 114 req.type = KMEM_KCM; 99 115 req.ptr = ptr2; 100 req.type = KMEM_GENERIC;101 req.size = sizeof(void *) * (1 << w2);102 116 kmem_free( &req ); 103 117 } 104 118 105 119 // release level 1 array 120 req.type = KMEM_KCM; 106 121 req.ptr = ptr1; 107 req.type = KMEM_GENERIC;108 req.size = sizeof(void *) * (1 << w1);109 122 kmem_free( &req ); 110 123 111 124 } // end grdxt_destroy() 112 113 ////////////////////////////////////114 void grdxt_display( xptr_t rt_xp,115 char * name )116 {117 uint32_t ix1;118 uint32_t ix2;119 uint32_t ix3;120 121 // check rt_xp122 assert( (rt_xp != XPTR_NULL) , "pointer on radix tree is NULL\n" );123 124 // get cluster and local pointer on remote rt descriptor125 grdxt_t * rt_ptr = GET_PTR( rt_xp );126 cxy_t rt_cxy = GET_CXY( rt_xp );127 128 // get widths129 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );130 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );131 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );132 133 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );134 135 printk("\n***** Generic Radix Tree for <%s>\n", name );136 137 for( ix1=0 ; ix1 < (uint32_t)(1<<w1) ; ix1++ )138 {139 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );140 if( ptr2 == NULL ) continue;141 142 for( ix2=0 ; ix2 < (uint32_t)(1<<w2) ; ix2++ )143 {144 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );145 if( ptr3 == NULL ) continue;146 147 for( ix3=0 ; ix3 < (uint32_t)(1<<w3) ; ix3++ )148 {149 void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );150 if( value == NULL ) continue;151 152 uint32_t key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3;153 printk(" - key = %x / value = %x\n", key , (intptr_t)value );154 }155 }156 }157 158 } // end grdxt_display()159 125 160 126 //////////////////////////////////// … … 177 143 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array 178 144 179 void ** ptr1 = rt->root; // pointer on level 1 array 180 void ** ptr2; // pointer on level 2 array 181 void ** ptr3; // pointer on level 3 array 182 183 // If required, we must allocate memory for the selected level 2 array, 184 // and update the level 1 array. 185 if( ptr1[ix1] == NULL ) 145 // get ptr1 146 void ** ptr1 = rt->root; 147 148 if( ptr1 == NULL ) return -1; 149 150 // get ptr2 151 void ** ptr2 = ptr1[ix1]; 152 153 // If required, allocate memory for the missing level 2 array 154 if( ptr2 == NULL ) 186 155 { 187 156 // allocate memory for level 2 array 188 req.type = KMEM_GENERIC;189 req. size = sizeof(void *) << w2;157 req.type = KMEM_KCM; 158 req.order = w2 + ( (sizeof(void*) == 4) ? 2 : 3 ); 190 159 req.flags = AF_KERNEL | AF_ZERO; 191 160 ptr2 = kmem_alloc( &req ); 192 if( ptr2 == NULL) return ENOMEM; 161 162 if( ptr2 == NULL) return -1; 193 163 194 164 // update level 1 array 195 165 ptr1[ix1] = ptr2; 196 166 } 197 else // get pointer on selected level 2 array. 198 { 199 ptr2 = ptr1[ix1]; 200 } 201 202 // If required, we must allocate memory for the selected level 3 array, 203 // and update the level 2 array. 204 if( ptr2[ix2] == NULL ) 167 168 // get ptr3 169 void ** ptr3 = ptr2[ix2]; 170 171 // If required, allocate memory for the missing level 3 array 172 if( ptr3 == NULL ) 205 173 { 206 174 // allocate memory for level 3 array 207 req.type = KMEM_ GENERIC;208 req. size = sizeof(void *) << w3;175 req.type = KMEM_KCM; 176 req.order = w3 + ( (sizeof(void*) == 4) ? 2 : 3 ); 209 177 req.flags = AF_KERNEL | AF_ZERO; 210 178 ptr3 = kmem_alloc( &req ); 211 if( ptr3 == NULL) return ENOMEM; 179 180 if( ptr3 == NULL) return -1; 212 181 213 182 // update level 3 array 214 183 ptr2[ix2] = ptr3; 215 184 } 216 else // get pointer on selected level 3 array.217 {218 ptr3 = ptr2[ix2];219 }220 221 // selected slot in level 3 array must be empty222 if( ptr3[ix3] != NULL ) return EEXIST;223 185 224 186 // register the value 225 187 ptr3[ix3] = value; 188 226 189 hal_fence(); 227 190 … … 246 209 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array 247 210 248 void ** ptr1 = rt->root; // pointer on level 1 array 249 void ** ptr2; // pointer on level 2 array 250 void ** ptr3; // pointer on level 3 array 211 // get ptr1 212 void ** ptr1 = rt->root; 213 214 if( ptr1 == NULL ) return NULL; 251 215 252 216 // get ptr2 253 ptr2 = ptr1[ix1]; 217 void ** ptr2 = ptr1[ix1]; 218 254 219 if( ptr2 == NULL ) return NULL; 255 220 256 221 // get ptr3 257 ptr3 = ptr2[ix2]; 222 void ** ptr3 = ptr2[ix2]; 223 258 224 if( ptr3 == NULL ) return NULL; 259 225 … … 303 269 304 270 } // end grdxt_lookup() 305 306 ////////////////////////////////////////////307 xptr_t grdxt_remote_lookup( xptr_t rt_xp,308 uint32_t key )309 {310 // get cluster and local pointer on remote rt descriptor311 grdxt_t * rt_ptr = GET_PTR( rt_xp );312 cxy_t rt_cxy = GET_CXY( rt_xp );313 314 // get widths315 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );316 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );317 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );318 319 // Check key value320 assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );321 322 // compute indexes323 uint32_t ix1 = key >> (w2 + w3); // index in level 1 array324 uint32_t ix2 = (key >> w3) & ((1 << w2) -1); // index in level 2 array325 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array326 327 // get ptr1328 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );329 330 // get ptr2331 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );332 if( ptr2 == NULL ) return XPTR_NULL;333 334 // get ptr3335 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );336 if( ptr3 == NULL ) return XPTR_NULL;337 338 // get pointer on registered item339 void * item_ptr = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );340 341 // return extended pointer on registered item342 if ( item_ptr == NULL ) return XPTR_NULL;343 else return XPTR( rt_cxy , item_ptr );344 345 } // end grdxt_remote_lookup()346 271 347 272 ////////////////////////////////////// … … 400 325 401 326 } // end grdxt_get_first() 327 328 329 330 //////////////////////////////////////////////////////////////////////////////////////// 331 // Remote access functions 332 //////////////////////////////////////////////////////////////////////////////////////// 333 334 ////////////////////////////////////////////// 335 error_t grdxt_remote_insert( xptr_t rt_xp, 336 uint32_t key, 337 void * value ) 338 { 339 kmem_req_t req; 340 341 // get cluster and local pointer on remote rt descriptor 342 cxy_t rt_cxy = GET_CXY( rt_xp ); 343 grdxt_t * rt_ptr = GET_PTR( rt_xp ); 344 345 // get widths 346 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) ); 347 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) ); 348 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) ); 349 350 // Check key value 351 assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key ); 352 353 // compute indexes 354 uint32_t ix1 = key >> (w2 + w3); // index in level 1 array 355 uint32_t ix2 = (key >> w3) & ((1 << w2) -1); // index in level 2 array 356 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array 357 358 // get ptr1 359 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) ); 360 361 if( ptr1 == NULL ) return -1; 362 363 // get ptr2 364 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) ); 365 366 // allocate memory for the missing level_2 array if required 367 if( ptr2 == NULL ) 368 { 369 // allocate memory in remote cluster 370 req.type = KMEM_KCM; 371 req.order = w2 + ((sizeof(void*) == 4) ? 2 : 3 ); 372 req.flags = AF_ZERO | AF_KERNEL; 373 ptr2 = kmem_remote_alloc( rt_cxy , &req ); 374 375 if( ptr2 == NULL ) return -1; 376 377 // update level_1 entry 378 hal_remote_spt( XPTR( rt_cxy , &ptr1[ix1] ) , ptr2 ); 379 } 380 381 // get ptr3 382 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) ); 383 384 // allocate memory for the missing level_3 array if required 385 if( ptr3 == NULL ) 386 { 387 // allocate memory in remote cluster 388 req.type = KMEM_KCM; 389 req.order = w3 + ((sizeof(void*) == 4) ? 2 : 3 ); 390 req.flags = AF_ZERO | AF_KERNEL; 391 ptr3 = kmem_remote_alloc( rt_cxy , &req ); 392 393 if( ptr3 == NULL ) return -1; 394 395 // update level_2 entry 396 hal_remote_spt( XPTR( rt_cxy , &ptr2[ix2] ) , ptr3 ); 397 } 398 399 // register value in level_3 array 400 hal_remote_spt( XPTR( rt_cxy , &ptr3[ix3] ) , value ); 401 402 hal_fence(); 403 404 return 0; 405 406 } // end grdxt_remote_insert() 407 408 //////////////////////////////////////////// 409 void * grdxt_remote_remove( xptr_t rt_xp, 410 uint32_t key ) 411 { 412 // get cluster and local pointer on remote rt descriptor 413 cxy_t rt_cxy = GET_CXY( rt_xp ); 414 grdxt_t * rt_ptr = GET_PTR( rt_xp ); 415 416 // get widths 417 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) ); 418 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) ); 419 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) ); 420 421 // Check key value 422 assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key ); 423 424 // compute indexes 425 uint32_t ix1 = key >> (w2 + w3); // index in level 1 array 426 uint32_t ix2 = (key >> w3) & ((1 << w2) -1); // index in level 2 array 427 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array 428 429 // get ptr1 430 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) ); 431 432 // get ptr2 433 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) ); 434 if( ptr2 == NULL ) return NULL; 435 436 // get ptr3 437 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) ); 438 if( ptr3 == NULL ) return NULL; 439 440 // get value 441 void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) ); 442 443 // reset selected slot 444 hal_remote_spt( XPTR( rt_cxy, &ptr3[ix3] ) , NULL ); 445 hal_fence(); 446 447 return value; 448 449 } // end grdxt_remote_remove() 450 451 //////////////////////////////////////////// 452 xptr_t grdxt_remote_lookup( xptr_t rt_xp, 453 uint32_t key ) 454 { 455 // get cluster and local pointer on remote rt descriptor 456 grdxt_t * rt_ptr = GET_PTR( rt_xp ); 457 cxy_t rt_cxy = GET_CXY( rt_xp ); 458 459 // get widths 460 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) ); 461 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) ); 462 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) ); 463 464 // Check key value 465 assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key ); 466 467 // compute indexes 468 uint32_t ix1 = key >> (w2 + w3); // index in level 1 array 469 uint32_t ix2 = (key >> w3) & ((1 << w2) -1); // index in level 2 array 470 uint32_t ix3 = key & ((1 << w3) - 1); // index in level 3 array 471 472 // get ptr1 473 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) ); 474 475 // get ptr2 476 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) ); 477 if( ptr2 == NULL ) return XPTR_NULL; 478 479 // get ptr3 480 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) ); 481 if( ptr3 == NULL ) return XPTR_NULL; 482 483 // get pointer on registered item 484 void * item_ptr = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) ); 485 486 // return extended pointer on registered item 487 if ( item_ptr == NULL ) return XPTR_NULL; 488 else return XPTR( rt_cxy , item_ptr ); 489 490 } // end grdxt_remote_lookup() 491 492 /////////////////////////i///////////////// 493 void grdxt_remote_display( xptr_t rt_xp, 494 char * name ) 495 { 496 uint32_t ix1; 497 uint32_t ix2; 498 uint32_t ix3; 499 500 // check rt_xp 501 assert( (rt_xp != XPTR_NULL) , "pointer on radix tree is NULL\n" ); 502 503 // get cluster and local pointer on remote rt descriptor 504 grdxt_t * rt_ptr = GET_PTR( rt_xp ); 505 cxy_t rt_cxy = GET_CXY( rt_xp ); 506 507 // get widths 508 uint32_t w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) ); 509 uint32_t w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) ); 510 uint32_t w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) ); 511 512 void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) ); 513 514 printk("\n***** Generic Radix Tree for <%s>\n", name ); 515 516 for( ix1=0 ; ix1 < (uint32_t)(1<<w1) ; ix1++ ) 517 { 518 void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) ); 519 if( ptr2 == NULL ) continue; 520 521 for( ix2=0 ; ix2 < (uint32_t)(1<<w2) ; ix2++ ) 522 { 523 void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) ); 524 if( ptr3 == NULL ) continue; 525 526 for( ix3=0 ; ix3 < (uint32_t)(1<<w3) ; ix3++ ) 527 { 528 void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) ); 529 if( value == NULL ) continue; 530 531 uint32_t key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3; 532 printk(" - key = %x / value = %x\n", key , (intptr_t)value ); 533 } 534 } 535 } 536 537 } // end grdxt_remote_display() 538 539
Note: See TracChangeset
for help on using the changeset viewer.