source: trunk/kernel/libk/grdxt.c @ 646

Last change on this file since 646 was 635, checked in by alain, 5 years ago

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 size: 15.1 KB
Line 
1/*
2 * grdxt.c - Three-levels Generic Radix-tree implementation.
3 *
4 * authors  Alain Greiner (2016,2017,2018,2019))
5 *
6 * Copyright (c)  UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <hal_kernel_types.h>
25#include <hal_special.h>
26#include <hal_remote.h>
27#include <errno.h>
28#include <printk.h>
29#include <kmem.h>
30#include <grdxt.h>
31
32////////////////////////////////////////////////////////////////////////////////////////
33//               Local access functions
34////////////////////////////////////////////////////////////////////////////////////////
35
36/////////////////////////////////
37error_t grdxt_init( grdxt_t * rt,
38                    uint32_t  ix1_width,
39                    uint32_t  ix2_width,
40                    uint32_t  ix3_width )
41{
42    void      ** root;
43        kmem_req_t   req;
44 
45        rt->ix1_width = ix1_width;
46        rt->ix2_width = ix2_width;
47        rt->ix3_width = ix3_width;
48
49    // allocates first level array
50        req.type  = KMEM_KCM;
51        req.order = ix1_width + ( (sizeof(void*) == 4) ? 2 : 3 );
52        req.flags = AF_KERNEL | AF_ZERO;
53        root = kmem_alloc( &req );
54
55        if( root == NULL )
56    {
57        printk("\n[ERROR] in %s : cannot allocate first level array\n", __FUNCTION__);
58        return -1;
59    }
60 
61        rt->root = root;
62
63        return 0;
64
65}  // end grdxt_init()
66
67//////////////////////////////////
68void grdxt_destroy( grdxt_t * rt )
69{
70        kmem_req_t req;
71
72    uint32_t   w1 = rt->ix1_width;
73    uint32_t   w2 = rt->ix2_width;
74    uint32_t   w3 = rt->ix3_width;
75
76    void    ** ptr1 = rt->root;
77    void    ** ptr2;
78    void    ** ptr3;
79
80        uint32_t   ix1;
81        uint32_t   ix2;
82        uint32_t   ix3;
83
84assert( (rt != NULL) , "pointer on radix tree is NULL\n" );
85
86        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
87        {
88        ptr2 = ptr1[ix1];
89
90                if( ptr2 == NULL ) continue;
91
92        for( ix2=0 ; ix2 < (uint32_t)(1 << w2) ; ix2++ )
93        {
94            ptr3 = ptr2[ix2];
95
96                    if( ptr3 == NULL ) continue;
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
107            // release level 3 array
108            req.type = KMEM_KCM;
109                    req.ptr  = ptr3;
110                    kmem_free( &req );
111        }
112
113        // release level 2 array
114        req.type = KMEM_KCM;
115                req.ptr  = ptr2;
116                kmem_free( &req );
117    }
118
119    // release level 1 array
120    req.type = KMEM_KCM;
121        req.ptr  = ptr1;
122        kmem_free( &req );
123
124}  // end grdxt_destroy()
125
126////////////////////////////////////
127error_t grdxt_insert( grdxt_t  * rt,
128                      uint32_t   key,
129                      void     * value )
130{
131        kmem_req_t      req;
132
133    uint32_t        w1 = rt->ix1_width;
134    uint32_t        w2 = rt->ix2_width;
135    uint32_t        w3 = rt->ix3_width;
136
137// Check key value
138assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
139
140    // compute indexes
141    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
142        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
143        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
144
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 )
155        {
156        // allocate memory for level 2 array
157        req.type  = KMEM_KCM;
158        req.order = w2 + ( (sizeof(void*) == 4) ? 2 : 3 );
159        req.flags = AF_KERNEL | AF_ZERO;
160        ptr2 = kmem_alloc( &req );
161
162        if( ptr2 == NULL) return -1;
163
164        // update level 1 array
165        ptr1[ix1] = ptr2;
166        }
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 )
173        {
174        // allocate memory for level 3 array
175        req.type = KMEM_KCM;
176        req.order = w3 + ( (sizeof(void*) == 4) ? 2 : 3 );
177        req.flags = AF_KERNEL | AF_ZERO;
178        ptr3 = kmem_alloc( &req );
179
180        if( ptr3 == NULL) return -1;
181
182        //  update level 3 array
183                ptr2[ix2] = ptr3;
184        }
185
186    // register the value
187        ptr3[ix3] = value;
188
189        hal_fence();
190
191        return 0;
192
193}  // end grdxt_insert()
194
195///////////////////////////////////
196void * grdxt_remove( grdxt_t  * rt,
197                     uint32_t   key )
198{
199    uint32_t        w1 = rt->ix1_width;
200    uint32_t        w2 = rt->ix2_width;
201    uint32_t        w3 = rt->ix3_width;
202
203// Check key value
204assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
205
206    // compute indexes
207    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
208        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
209        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
210
211    // get ptr1
212    void ** ptr1 = rt->root;
213
214    if( ptr1 == NULL ) return NULL;
215
216    // get ptr2
217        void ** ptr2 = ptr1[ix1];
218
219        if( ptr2 == NULL ) return NULL;
220
221    // get ptr3
222        void ** ptr3 = ptr2[ix2];
223
224        if( ptr3 == NULL ) return NULL;
225
226    // get value
227        void * value = ptr3[ix3];
228
229    // reset selected slot
230        ptr3[ix3] = NULL;
231        hal_fence();
232
233        return value;
234
235}  // end grdxt_remove()
236
237///////////////////////////////////
238void * grdxt_lookup( grdxt_t  * rt,
239                     uint32_t   key )
240{
241    uint32_t        w1 = rt->ix1_width;
242    uint32_t        w2 = rt->ix2_width;
243    uint32_t        w3 = rt->ix3_width;
244
245// Check key value
246assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
247
248    void         ** ptr1 = rt->root;
249    void         ** ptr2;
250    void         ** ptr3;
251
252    // compute indexes
253    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
254        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
255        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
256
257    // get ptr2
258        ptr2 = ptr1[ix1];
259        if( ptr2 == NULL ) return NULL;
260
261    // get ptr3
262        ptr3 = ptr2[ix2];
263        if( ptr3 == NULL ) return NULL;
264
265    // get value
266        void * value = ptr3[ix3];
267
268        return value;
269
270}  // end grdxt_lookup()
271
272//////////////////////////////////////
273void * grdxt_get_first( grdxt_t  * rt,
274                        uint32_t   start_key,
275                        uint32_t * found_key )
276{
277    uint32_t        ix1;
278    uint32_t        ix2;
279    uint32_t        ix3;
280
281    uint32_t        w1 = rt->ix1_width;
282    uint32_t        w2 = rt->ix2_width;
283    uint32_t        w3 = rt->ix3_width;
284
285// Check key value
286assert( ((start_key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", start_key );
287
288    // compute max indexes
289    uint32_t        max1 = 1 << w1;
290    uint32_t        max2 = 1 << w2;
291    uint32_t        max3 = 1 << w3;
292
293    // compute min indexes
294    uint32_t        min1 = start_key >> (w2 + w3);           
295        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
296        uint32_t        min3 = start_key & ((1 << w3) - 1); 
297
298    void         ** ptr1 = rt->root;
299    void         ** ptr2;
300    void         ** ptr3;
301
302    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
303    {
304        ptr2 = ptr1[ix1];
305        if( ptr2 == NULL ) continue;
306
307        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
308        {
309            ptr3 = ptr2[ix2];
310            if( ptr3 == NULL ) continue;
311
312            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
313            {
314                if( ptr3[ix3] == NULL ) continue;
315                else                   
316                {
317                    *found_key = (ix1 << (w2+w3)) | (ix2 << w1) | ix3;
318                    return ptr3[ix3];
319                }
320            }
321        }
322    }
323
324    return NULL;
325
326}  // 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 TracBrowser for help on using the repository browser.