Ignore:
Timestamp:
Jun 26, 2019, 11:42:37 AM (5 years ago)
Author:
alain
Message:

This version is a major evolution: The physical memory allocators,
defined in the kmem.c, ppm.c, and kcm.c files have been modified
to support remote accesses. The RPCs that were previously user
to allocate physical memory in a remote cluster have been removed.
This has been done to cure a dead-lock in case of concurrent page-faults.

This version 2.2 has been tested on a (4 clusters / 2 cores per cluster)
TSAR architecture, for both the "sort" and the "fft" applications.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/kernel/libk/grdxt.c

    r626 r635  
    3030#include <grdxt.h>
    3131
     32////////////////////////////////////////////////////////////////////////////////////////
     33//               Local access functions
     34////////////////////////////////////////////////////////////////////////////////////////
     35
    3236/////////////////////////////////
    3337error_t grdxt_init( grdxt_t * rt,
    … …  
    4448
    4549    // 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 );
    4852        req.flags = AF_KERNEL | AF_ZERO;
    4953        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    }
    5160 
    5261        rt->root = root;
    … …  
    7180        uint32_t   ix1;
    7281        uint32_t   ix2;
    73 
    74 // check rt
     82        uint32_t   ix3;
     83
    7584assert( (rt != NULL) , "pointer on radix tree is NULL\n" );
    76 
    77         req.type = KMEM_GENERIC;
    7885
    7986        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
    … …  
    8996                    if( ptr3 == NULL ) continue;
    9097
     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
    91107            // release level 3 array
     108            req.type = KMEM_KCM;
    92109                    req.ptr  = ptr3;
    93             req.type = KMEM_GENERIC;
    94             req.size = sizeof(void *) * (1 << w3);
    95110                    kmem_free( &req );
    96111        }
    97112
    98113        // release level 2 array
     114        req.type = KMEM_KCM;
    99115                req.ptr  = ptr2;
    100         req.type = KMEM_GENERIC;
    101         req.size = sizeof(void *) * (1 << w2);
    102116                kmem_free( &req );
    103117    }
    104118
    105119    // release level 1 array
     120    req.type = KMEM_KCM;
    106121        req.ptr  = ptr1;
    107     req.type = KMEM_GENERIC;
    108     req.size = sizeof(void *) * (1 << w1);
    109122        kmem_free( &req );
    110123
    111124}  // 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_xp
    122 assert( (rt_xp != XPTR_NULL) , "pointer on radix tree is NULL\n" );
    123 
    124     // get cluster and local pointer on remote rt descriptor
    125     grdxt_t      * rt_ptr = GET_PTR( rt_xp );
    126     cxy_t          rt_cxy = GET_CXY( rt_xp );
    127 
    128     // get widths
    129     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()
    159125
    160126////////////////////////////////////
    … …  
    177143        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
    178144
    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 )
    186155        {
    187156        // 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 );
    190159        req.flags = AF_KERNEL | AF_ZERO;
    191160        ptr2 = kmem_alloc( &req );
    192         if( ptr2 == NULL) return ENOMEM;
     161
     162        if( ptr2 == NULL) return -1;
    193163
    194164        // update level 1 array
    195165        ptr1[ix1] = ptr2;
    196166        }
    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 )
    205173        {
    206174        // 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 );
    209177        req.flags = AF_KERNEL | AF_ZERO;
    210178        ptr3 = kmem_alloc( &req );
    211         if( ptr3 == NULL) return ENOMEM;
     179
     180        if( ptr3 == NULL) return -1;
    212181
    213182        //  update level 3 array
    214183                ptr2[ix2] = ptr3;
    215184        }
    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 empty
    222         if( ptr3[ix3] != NULL ) return EEXIST;
    223185
    224186    // register the value
    225187        ptr3[ix3] = value;
     188
    226189        hal_fence();
    227190
    … …  
    246209        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
    247210
    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;
    251215
    252216    // get ptr2
    253         ptr2 = ptr1[ix1];
     217        void ** ptr2 = ptr1[ix1];
     218
    254219        if( ptr2 == NULL ) return NULL;
    255220
    256221    // get ptr3
    257         ptr3 = ptr2[ix2];
     222        void ** ptr3 = ptr2[ix2];
     223
    258224        if( ptr3 == NULL ) return NULL;
    259225
    … …  
    303269
    304270}  // 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 descriptor
    311     grdxt_t       * rt_ptr = GET_PTR( rt_xp );
    312     cxy_t           rt_cxy = GET_CXY( rt_xp );
    313 
    314     // get widths
    315     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 value
    320 assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
    321 
    322     // compute indexes
    323     uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
    324         uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
    325         uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
    326 
    327     // get ptr1
    328     void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
    329 
    330     // get ptr2
    331         void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
    332         if( ptr2 == NULL ) return XPTR_NULL;
    333 
    334     // get ptr3
    335         void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
    336         if( ptr3 == NULL ) return XPTR_NULL;
    337 
    338     // get pointer on registered item
    339     void  * item_ptr = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
    340 
    341     // return extended pointer on registered item
    342     if ( item_ptr == NULL )  return XPTR_NULL;
    343         else                     return XPTR( rt_cxy , item_ptr );
    344 
    345 }  // end grdxt_remote_lookup()
    346271
    347272//////////////////////////////////////
    … …  
    400325
    401326}  // end grdxt_get_first()
     327
     328
     329
     330////////////////////////////////////////////////////////////////////////////////////////
     331//               Remote access functions
     332////////////////////////////////////////////////////////////////////////////////////////
     333
     334//////////////////////////////////////////////
     335error_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
     351assert( ((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////////////////////////////////////////////
     409void * 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
     422assert( ((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////////////////////////////////////////////
     452xptr_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
     465assert( ((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/////////////////
     493void 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
     501assert( (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.