source: trunk/kernel/kern/dqdt.c @ 571

Last change on this file since 571 was 564, checked in by alain, 5 years ago

Complete restructuration of kernel locks.

File size: 12.4 KB
Line 
1/*
2 * dqdt.c - Distributed Quaternary Decision Tree implementation.
3 *
4 * Author : Alain Greiner (2016,2017,2018)
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 <kernel_config.h>
25#include <hal_kernel_types.h>
26#include <hal_special.h>
27#include <hal_atomic.h>
28#include <hal_remote.h>
29#include <printk.h>
30#include <chdev.h>
31#include <cluster.h>
32#include <bits.h>
33#include <dqdt.h>
34
35
36///////////////////////////////////////////////////////////////////////////////////////////
37//      Extern variables
38///////////////////////////////////////////////////////////////////////////////////////////
39
40extern chdev_directory_t  chdev_dir;  // defined in chdev.h / allocated in kernel_init.c
41
42/*
43///////////////////////////////////////////////////////////////////////////////////////////
44// This static recursive function traverse the DQDT quad-tree from root to bottom.
45///////////////////////////////////////////////////////////////////////////////////////////
46static void dqdt_recursive_print( xptr_t  node_xp )
47{
48        uint32_t i;
49    dqdt_node_t node;
50
51    // get node local copy
52    hal_remote_memcpy( XPTR( local_cxy , &node ), node_xp , sizeof(dqdt_node_t) );
53
54    // display node content
55        nolock_printk("- level %d in cluster %x (node %x) : threads = %x / pages = %x\n",
56    node.level, GET_CXY( node_xp ), GET_PTR( node_xp ), node.threads, node.pages );
57
58    // recursive call on children if node is not terminal
59    if ( node.level > 0 )
60    {
61        for ( i = 0 ; i < 4 ; i++ )
62        {
63            if ( node.children[i] != XPTR_NULL ) dqdt_recursive_print( node.children[i] );
64        }
65    }
66}
67*/
68
69/////////////////////////
70void dqdt_display( void )
71{
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] );
79
80    // get pointers on TXT0 chdev
81    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
82    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
83    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
84
85    // get extended pointer on remote TXT0 lock
86    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
87
88    // get TXT0 lock
89    remote_busylock_acquire( lock_xp );
90
91    // print header
92    nolock_printk("\n***** DQDT state\n\n");
93
94    // call recursive function
95    dqdt_recursive_print( root_xp );
96
97    // release lock
98    remote_busylock_release( lock_xp );
99*/
100
101}
102
103////////////////////////////////////
104uint32_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");
108 
109    // compute level_max
110    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
111    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
115return 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/*
202///////////////////////////////////////////////////////////////////////////
203// This recursive function is called by the dqdt_update_threads() function.
204// It traverses the quad tree from clusters to root.
205///////////////////////////////////////////////////////////////////////////
206// @ node       : extended pointer on current node
207// @ increment  : number of threads variation
208///////////////////////////////////////////////////////////////////////////
209static void dqdt_propagate_threads( xptr_t  node,
210                                    int32_t increment )
211{
212    // get current node cluster identifier and local pointer
213    cxy_t         cxy = GET_CXY( node );
214    dqdt_node_t * ptr = GET_PTR( node );
215
216    // update current node threads number
217    hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , increment );
218
219    // get extended pointer on parent node
220    xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) );
221
222    // propagate if required
223    if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
224}
225*/
226
227/*
228///////////////////////////////////////////////////////////////////////////
229// This recursive function is called by the dqdt_update_pages() function.
230// It traverses the quad tree from clusters to root.
231///////////////////////////////////////////////////////////////////////////
232// @ node       : extended pointer on current node
233// @ increment  : number of pages variation
234///////////////////////////////////////////////////////////////////////////
235static void dqdt_propagate_pages( xptr_t  node,
236                                  int32_t increment )
237{
238    // get current node cluster identifier and local pointer
239    cxy_t         cxy = GET_CXY( node );
240    dqdt_node_t * ptr = GET_PTR( node );
241
242    // update current node threads number
243    hal_remote_atomic_add( XPTR( cxy , &ptr->pages ) , increment );
244
245    // get extended pointer on parent node
246    xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) );
247
248    // propagate if required
249    if ( parent != XPTR_NULL ) dqdt_propagate_pages( parent, increment );
250}
251*/
252
253/////////////////////////////////////////////
254void dqdt_update_threads( int32_t increment __attribute__ ((__unused__)) )
255{
256
257return;
258
259/*
260        cluster_t   * cluster = LOCAL_CLUSTER;
261    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
262
263    // update DQDT node level 0
264    hal_atomic_add( &node->threads , increment );
265
266    // propagate to DQDT upper levels
267    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment );
268*/
269
270}
271
272///////////////////////////////////////////
273void dqdt_update_pages( int32_t increment  __attribute__ ((__unused__)) )
274{
275
276return;
277
278/*
279        cluster_t   * cluster = LOCAL_CLUSTER;
280    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
281
282    // update DQDT node level 0
283    hal_atomic_add( &node->pages , increment );
284
285    // propagate to DQDT upper levels
286    if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment );
287*/
288
289}
290
291/*
292////////////////////////////////////////////////////////////////////////////////
293// This recursive function is called by both the dqdt_get_cluster_for_process()
294// and by the dqdt_get_cluster_for_memory() functions to select the cluster
295// with smallest number of thread, or smallest number of allocated pages.
296// It traverses the quad tree from root to clusters.
297///////////////////////////////////////////////////////////////////////////////
298static cxy_t dqdt_select_cluster( xptr_t node,
299                                  bool_t for_memory )
300{
301    dqdt_node_t   node_copy;     // local copy of the current DQDT node
302    uint32_t      i;             // index in the loop on children
303    uint32_t      select;        // index of selected child
304    xptr_t        child;         // extended pointer on a DQDT child node
305    cxy_t         cxy;           // DQDT child node cluster identifier
306    dqdt_node_t * ptr;           // pointer on a DQDT child node
307    uint32_t      load;          // load of the child (threads or pages)
308    uint32_t      load_min;      // current value of the minimal load
309
310    // get DQDT node local copy
311    hal_remote_memcpy( XPTR( local_cxy , &node_copy ), node , sizeof(dqdt_node_t) );
312
313    // return cluster identifier for a terminal mode
314    if( node_copy.level == 0 ) return GET_CXY(node);
315
316    // analyse load for all children in non terminal node
317    load_min = 0xFFFFFFFF;
318    select   = 0;
319    for( i = 0 ; i < 4 ; i++ )
320    {
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;
332            }
333        }
334    }
335
336    // select the child with the lowest load
337    return dqdt_select_cluster( node_copy.children[select], for_memory );
338}
339*/
340
341//////////////////////////////////////////
342cxy_t dqdt_get_cluster_for_process( void )
343{
344
345return cluster_random_select();
346
347/*
348    // build extended pointer on DQDT root node
349        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    // call recursive function
354    return dqdt_select_cluster( root_xp , false );
355*/
356
357}
358
359/////////////////////////////////////////
360cxy_t dqdt_get_cluster_for_memory( void )
361{
362
363return cluster_random_select();
364 
365/*
366    // build extended pointer on DQDT root node
367        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    // call recursive function
372    return dqdt_select_cluster( root_xp , true );
373*/
374
375}
376
Note: See TracBrowser for help on using the repository browser.