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

Last change on this file since 629 was 626, checked in by alain, 5 years ago

This version has been tested on the sort multithreaded application
for TSAR_IOB architectures ranging from 1 to 8 clusters.
It fixes three bigs bugs:
1) the dev_ioc device API has been modified: the dev_ioc_sync_read()
and dev_ioc_sync_write() function use now extended pointers on the
kernel buffer to access a mapper stored in any cluster.
2) the hal_uspace API has been modified: the hal_copy_to_uspace()
and hal_copy_from_uspace() functions use now a (cxy,ptr) couple
to identify the target buffer (equivalent to an extended pointer.
3) an implementation bug has been fixed in the assembly code contained
in the hal_copy_to_uspace() and hal_copy_from_uspace() functions.

File size: 11.3 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/////////////////////////////////
33error_t grdxt_init( grdxt_t * rt,
34                    uint32_t  ix1_width,
35                    uint32_t  ix2_width,
36                    uint32_t  ix3_width )
37{
38    void      ** root;
39        kmem_req_t   req;
40 
41        rt->ix1_width = ix1_width;
42        rt->ix2_width = ix2_width;
43        rt->ix3_width = ix3_width;
44
45    // allocates first level array
46        req.type  = KMEM_GENERIC;
47        req.size  = sizeof(void *) << ix1_width;
48        req.flags = AF_KERNEL | AF_ZERO;
49        root = kmem_alloc( &req );
50        if( root == NULL ) return ENOMEM;
51 
52        rt->root = root;
53
54        return 0;
55
56}  // end grdxt_init()
57
58//////////////////////////////////
59void grdxt_destroy( grdxt_t * rt )
60{
61        kmem_req_t req;
62
63    uint32_t   w1 = rt->ix1_width;
64    uint32_t   w2 = rt->ix2_width;
65    uint32_t   w3 = rt->ix3_width;
66
67    void    ** ptr1 = rt->root;
68    void    ** ptr2;
69    void    ** ptr3;
70
71        uint32_t   ix1;
72        uint32_t   ix2;
73
74// check rt
75assert( (rt != NULL) , "pointer on radix tree is NULL\n" );
76
77        req.type = KMEM_GENERIC;
78
79        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
80        {
81        ptr2 = ptr1[ix1];
82
83                if( ptr2 == NULL ) continue;
84
85        for( ix2=0 ; ix2 < (uint32_t)(1 << w2) ; ix2++ )
86        {
87            ptr3 = ptr2[ix2];
88
89                    if( ptr3 == NULL ) continue;
90
91            // release level 3 array
92                    req.ptr  = ptr3;
93            req.type = KMEM_GENERIC;
94            req.size = sizeof(void *) * (1 << w3);
95                    kmem_free( &req );
96        }
97
98        // release level 2 array
99                req.ptr  = ptr2;
100        req.type = KMEM_GENERIC;
101        req.size = sizeof(void *) * (1 << w2);
102                kmem_free( &req );
103    }
104
105    // release level 1 array
106        req.ptr  = ptr1;
107    req.type = KMEM_GENERIC;
108    req.size = sizeof(void *) * (1 << w1);
109        kmem_free( &req );
110
111}  // end grdxt_destroy()
112
113////////////////////////////////////
114void 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
122assert( (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()
159
160////////////////////////////////////
161error_t grdxt_insert( grdxt_t  * rt,
162                      uint32_t   key,
163                      void     * value )
164{
165        kmem_req_t      req;
166
167    uint32_t        w1 = rt->ix1_width;
168    uint32_t        w2 = rt->ix2_width;
169    uint32_t        w3 = rt->ix3_width;
170
171// Check key value
172assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
173
174    // compute indexes
175    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
176        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
177        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
178
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 )
186        {
187        // allocate memory for level 2 array
188        req.type = KMEM_GENERIC;
189        req.size = sizeof(void *) << w2;
190        req.flags = AF_KERNEL | AF_ZERO;
191        ptr2 = kmem_alloc( &req );
192        if( ptr2 == NULL) return ENOMEM;
193
194        // update level 1 array
195        ptr1[ix1] = ptr2;
196        }
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 )
205        {
206        // allocate memory for level 3 array
207        req.type = KMEM_GENERIC;
208        req.size = sizeof(void *) << w3;
209        req.flags = AF_KERNEL | AF_ZERO;
210        ptr3 = kmem_alloc( &req );
211        if( ptr3 == NULL) return ENOMEM;
212
213        //  update level 3 array
214                ptr2[ix2] = ptr3;
215        }
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;
223
224    // register the value
225        ptr3[ix3] = value;
226        hal_fence();
227
228        return 0;
229
230}  // end grdxt_insert()
231
232///////////////////////////////////
233void * grdxt_remove( grdxt_t  * rt,
234                     uint32_t   key )
235{
236    uint32_t        w1 = rt->ix1_width;
237    uint32_t        w2 = rt->ix2_width;
238    uint32_t        w3 = rt->ix3_width;
239
240// Check key value
241assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
242
243    // compute indexes
244    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
245        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
246        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
247
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
251
252    // get ptr2
253        ptr2 = ptr1[ix1];
254        if( ptr2 == NULL ) return NULL;
255
256    // get ptr3
257        ptr3 = ptr2[ix2];
258        if( ptr3 == NULL ) return NULL;
259
260    // get value
261        void * value = ptr3[ix3];
262
263    // reset selected slot
264        ptr3[ix3] = NULL;
265        hal_fence();
266
267        return value;
268
269}  // end grdxt_remove()
270
271///////////////////////////////////
272void * grdxt_lookup( grdxt_t  * rt,
273                     uint32_t   key )
274{
275    uint32_t        w1 = rt->ix1_width;
276    uint32_t        w2 = rt->ix2_width;
277    uint32_t        w3 = rt->ix3_width;
278
279// Check key value
280assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
281
282    void         ** ptr1 = rt->root;
283    void         ** ptr2;
284    void         ** ptr3;
285
286    // compute indexes
287    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
288        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
289        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
290
291    // get ptr2
292        ptr2 = ptr1[ix1];
293        if( ptr2 == NULL ) return NULL;
294
295    // get ptr3
296        ptr3 = ptr2[ix2];
297        if( ptr3 == NULL ) return NULL;
298
299    // get value
300        void * value = ptr3[ix3];
301
302        return value;
303
304}  // end grdxt_lookup()
305
306////////////////////////////////////////////
307xptr_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
320assert( ((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()
346
347//////////////////////////////////////
348void * grdxt_get_first( grdxt_t  * rt,
349                        uint32_t   start_key,
350                        uint32_t * found_key )
351{
352    uint32_t        ix1;
353    uint32_t        ix2;
354    uint32_t        ix3;
355
356    uint32_t        w1 = rt->ix1_width;
357    uint32_t        w2 = rt->ix2_width;
358    uint32_t        w3 = rt->ix3_width;
359
360// Check key value
361assert( ((start_key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", start_key );
362
363    // compute max indexes
364    uint32_t        max1 = 1 << w1;
365    uint32_t        max2 = 1 << w2;
366    uint32_t        max3 = 1 << w3;
367
368    // compute min indexes
369    uint32_t        min1 = start_key >> (w2 + w3);           
370        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
371        uint32_t        min3 = start_key & ((1 << w3) - 1); 
372
373    void         ** ptr1 = rt->root;
374    void         ** ptr2;
375    void         ** ptr3;
376
377    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
378    {
379        ptr2 = ptr1[ix1];
380        if( ptr2 == NULL ) continue;
381
382        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
383        {
384            ptr3 = ptr2[ix2];
385            if( ptr3 == NULL ) continue;
386
387            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
388            {
389                if( ptr3[ix3] == NULL ) continue;
390                else                   
391                {
392                    *found_key = (ix1 << (w2+w3)) | (ix2 << w1) | ix3;
393                    return ptr3[ix3];
394                }
395            }
396        }
397    }
398
399    return NULL;
400
401}  // end grdxt_get_first()
Note: See TracBrowser for help on using the repository browser.