source: trunk/kernel/libk/remote_barrier.c @ 679

Last change on this file since 679 was 671, checked in by alain, 4 years ago

Cosmetic.
File size: 38.5 KB
Line 
1/*
2 * remote_barrier.c -  POSIX barrier implementation.
3 *
4 * Author   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_macros.h>
26#include <hal_remote.h>
27#include <hal_irqmask.h>
28#include <remote_busylock.h>
29#include <thread.h>
30#include <kmem.h>
31#include <printk.h>
32#include <process.h>
33#include <vmm.h>
34#include <remote_barrier.h>
35
36////////////////////////////////////////////////////
37//  generic (implementation independant) functions
38////////////////////////////////////////////////////
39
40///////////////////////////////////////////////////
41xptr_t generic_barrier_from_ident( intptr_t  ident )
42{
43    // get pointer on local process_descriptor
44    process_t * process = CURRENT_THREAD->process;
45
46    // get pointers on reference process
47    xptr_t         ref_xp  = process->ref_xp;
48    cxy_t          ref_cxy = GET_CXY( ref_xp );
49    process_t    * ref_ptr = (process_t *)GET_PTR( ref_xp );
50
51    // get extended pointer on root of barriers list
52    xptr_t root_xp = XPTR( ref_cxy , &ref_ptr->barrier_root );
53
54    // scan reference process barriers list
55    xptr_t              iter_xp;
56    xptr_t              barrier_xp;
57    cxy_t               barrier_cxy;
58    generic_barrier_t * barrier_ptr;
59    intptr_t            current;
60    bool_t              found = false;
61
62    XLIST_FOREACH( root_xp , iter_xp )
63    {
64        barrier_xp  = XLIST_ELEMENT( iter_xp , generic_barrier_t , list );
65        barrier_cxy = GET_CXY( barrier_xp );
66        barrier_ptr = (generic_barrier_t *)GET_PTR( barrier_xp );
67        current     = (intptr_t)hal_remote_lpt( XPTR( barrier_cxy , &barrier_ptr->ident ) );
68        if( ident == current )
69        {
70            found = true;
71            break;
72        }
73    }
74
75    if( found == false )  return XPTR_NULL;
76    else                  return barrier_xp;
77
78} // end generic_barrier_from_ident()
79
80//////////////////////////////////////////////////////////////
81error_t generic_barrier_create( intptr_t                ident,
82                                uint32_t                count,
83                                pthread_barrierattr_t * attr )
84{
85    generic_barrier_t * gen_barrier_ptr;  // local pointer on generic barrier descriptor
86    void              * barrier;          // local pointer on implementation barrier descriptor     
87    kmem_req_t          req;              // kmem request
88
89    // get pointer on local process_descriptor
90    process_t * process = CURRENT_THREAD->process;
91
92    // get pointers on reference process
93    xptr_t         ref_xp  = process->ref_xp;
94    cxy_t          ref_cxy = GET_CXY( ref_xp );
95    process_t    * ref_ptr = (process_t *)GET_PTR( ref_xp );
96
97    // allocate memory for generic barrier descriptor
98    req.type   = KMEM_KCM;
99    req.order  = bits_log2( sizeof(generic_barrier_t) );
100    req.flags  = AF_ZERO | AF_KERNEL;
101    gen_barrier_ptr = kmem_remote_alloc( ref_cxy , &req );
102
103    if( gen_barrier_ptr == NULL )
104    {
105        printk("\n[ERROR] in %s : cannot create generic barrier\n", __FUNCTION__ );
106        return -1;
107    }
108
109    // create implementation specific barrier descriptor
110    if( attr == NULL )                                    // simple barrier implementation
111    {
112        // create simple barrier descriptor
113         barrier = simple_barrier_create( count );
114
115        if( barrier == NULL ) return -1;
116    }
117    else                                                  // QDT barrier implementation
118    {
119        uint32_t x_size   = attr->x_size;
120        uint32_t y_size   = attr->y_size;
121        uint32_t nthreads = attr->nthreads;
122
123        // check attributes / count
124        if( (x_size * y_size * nthreads) != count )
125        {
126            printk("\n[ERROR] in %s : count(%d) != x_size(%d) * y_size(%d) * nthreads(%d)\n",
127            __FUNCTION__, count, x_size, y_size, nthreads );
128            return -1;
129        }
130
131        // create DQT barrier descriptor
132        barrier = dqt_barrier_create( x_size , y_size , nthreads );
133
134        if( barrier == NULL ) return -1;
135    }
136
137    // initialize the generic barrier descriptor
138    hal_remote_spt( XPTR( ref_cxy , &gen_barrier_ptr->ident  ) , (void*)ident );
139    hal_remote_s32( XPTR( ref_cxy , &gen_barrier_ptr->is_dqt ) , (attr != NULL) );
140    hal_remote_spt( XPTR( ref_cxy , &gen_barrier_ptr->extend ) , barrier );
141
142    // build extended pointers on lock, root and entry for reference process xlist
143    xptr_t root_xp  = XPTR( ref_cxy , &ref_ptr->barrier_root );
144    xptr_t lock_xp  = XPTR( ref_cxy , &ref_ptr->sync_lock );
145    xptr_t entry_xp = XPTR( ref_cxy , &gen_barrier_ptr->list );
146
147    // register barrier in reference process xlist of barriers
148    remote_busylock_acquire( lock_xp );
149    xlist_add_first( root_xp , entry_xp );
150    remote_busylock_release( lock_xp );
151
152    return 0;
153
154}  // en generic_barrier_create()
155
156/////////////////////////////////////////////////////
157void generic_barrier_destroy( xptr_t gen_barrier_xp )
158{
159    kmem_req_t  req;              // kmem request
160
161    // get pointer on local process_descriptor
162    process_t * process = CURRENT_THREAD->process;
163
164    // get pointers on reference process
165    xptr_t      ref_xp  = process->ref_xp;
166    cxy_t       ref_cxy = GET_CXY( ref_xp );
167    process_t * ref_ptr = GET_PTR( ref_xp );
168
169    // get cluster and local pointer on generic barrier descriptor
170    generic_barrier_t * gen_barrier_ptr = GET_PTR( gen_barrier_xp );
171    cxy_t               gen_barrier_cxy = GET_CXY( gen_barrier_xp );
172
173    // get barrier type and extension pointer
174    bool_t  is_dqt = hal_remote_l32( XPTR( gen_barrier_cxy , &gen_barrier_ptr->is_dqt ) );
175    void  * extend = hal_remote_lpt( XPTR( gen_barrier_cxy , &gen_barrier_ptr->extend ) );
176
177    // build extended pointer on implementation dependant barrier descriptor
178    xptr_t barrier_xp = XPTR( gen_barrier_cxy , extend );
179
180    // delete the implementation specific barrier
181    if( is_dqt ) dqt_barrier_destroy( barrier_xp );
182    else         simple_barrier_destroy( barrier_xp );
183
184    // build extended pointers on lock and entry for reference process xlist
185    xptr_t  lock_xp  = XPTR( ref_cxy , &ref_ptr->sync_lock );
186    xptr_t  entry_xp = XPTR( gen_barrier_cxy , &gen_barrier_ptr->list );
187
188    // remove barrier from reference process xlist
189    remote_busylock_acquire( lock_xp );
190    xlist_unlink( entry_xp );
191    remote_busylock_release( lock_xp );
192
193    // release memory allocated to barrier descriptor
194    req.type          = KMEM_KCM;
195    req.ptr           = gen_barrier_ptr;
196    kmem_remote_free( ref_cxy , &req );
197
198}  // end generic_barrier_destroy()
199
200//////////////////////////////////////////////////
201void generic_barrier_wait( xptr_t gen_barrier_xp )
202{
203    // get generic barrier descriptor cluster and pointer
204    cxy_t               gen_barrier_cxy = GET_CXY( gen_barrier_xp );
205    generic_barrier_t * gen_barrier_ptr = GET_PTR( gen_barrier_xp );
206
207    // get implementation type and extend local pointer
208    bool_t  is_dqt = hal_remote_l32( XPTR( gen_barrier_cxy , &gen_barrier_ptr->is_dqt ) );
209    void  * extend = hal_remote_lpt( XPTR( gen_barrier_cxy , &gen_barrier_ptr->extend ) );
210
211    // build extended pointer on implementation specific barrier descriptor
212    xptr_t barrier_xp = XPTR( gen_barrier_cxy , extend );
213
214    // call the relevant wait function
215    if( is_dqt ) dqt_barrier_wait( barrier_xp );
216    else         simple_barrier_wait( barrier_xp );
217   
218}  // end generic_barrier_wait()
219
220/////////////////////////////////////////////////////
221void generic_barrier_display( xptr_t gen_barrier_xp )
222{
223    // get cluster and local pointer
224    generic_barrier_t * gen_barrier_ptr = GET_PTR( gen_barrier_xp );
225    cxy_t               gen_barrier_cxy = GET_CXY( gen_barrier_xp );
226
227    // get barrier type and extend pointer
228    bool_t  is_dqt = hal_remote_l32( XPTR( gen_barrier_cxy , &gen_barrier_ptr->is_dqt ) );
229    void  * extend = hal_remote_lpt( XPTR( gen_barrier_cxy , &gen_barrier_ptr->extend ) );
230
231    // buil extended pointer on the implementation specific barrier descriptor
232    xptr_t barrier_xp = XPTR( gen_barrier_cxy , extend );
233
234    // display barrier state
235    if( is_dqt ) dqt_barrier_display( barrier_xp );
236    else         simple_barrier_display( barrier_xp );
237}
238
239
240
241/////////////////////////////////////////////////////////////
242//      simple barrier functions
243/////////////////////////////////////////////////////////////
244
245///////////////////////////////////////////////////////////
246simple_barrier_t * simple_barrier_create( uint32_t  count )
247{
248    kmem_req_t         req;
249    simple_barrier_t * barrier;
250
251    // get pointer on local client process descriptor
252    thread_t  * this    = CURRENT_THREAD;
253    process_t * process = this->process;
254
255    // get reference process cluster
256    xptr_t         ref_xp  = process->ref_xp;
257    cxy_t          ref_cxy = GET_CXY( ref_xp );
258
259    // allocate memory for simple barrier descriptor
260    req.type   = KMEM_KCM;
261    req.order  = bits_log2( sizeof(simple_barrier_t) );
262    req.flags  = AF_ZERO | AF_KERNEL;
263    barrier    = kmem_remote_alloc( ref_cxy , &req );
264
265    if( barrier == NULL )
266    {
267        printk("\n[ERROR] in %s : cannot create simple barrier\n", __FUNCTION__ );
268        return NULL;
269    }
270
271    // initialise simple barrier descriptor
272    hal_remote_s32      ( XPTR( ref_cxy , &barrier->arity )      , count );
273    hal_remote_s32      ( XPTR( ref_cxy , &barrier->current    ) , 0 );
274    hal_remote_s32      ( XPTR( ref_cxy , &barrier->sense      ) , 0 );
275
276    xlist_root_init     ( XPTR( ref_cxy , &barrier->root ) );
277    remote_busylock_init( XPTR( ref_cxy , &barrier->lock ) , LOCK_BARRIER_STATE );
278
279#if DEBUG_BARRIER_CREATE
280uint32_t cycle = (uint32_t)hal_get_cycles();
281if( cycle > DEBUG_BARRIER_CREATE )
282printk("\n[%s] thread[%x,%x] created barrier (%x,%x) / count %d / cycle %d\n",
283__FUNCTION__, process->pid, this->trdid, ref_cxy, barrier, count, cycle );
284#endif
285
286    return barrier;
287
288}  // end simple_barrier_create()
289
290////////////////////////////////////////////////
291void simple_barrier_destroy( xptr_t barrier_xp )
292{
293    kmem_req_t  req;
294
295    // get barrier cluster and local pointer
296    cxy_t              barrier_cxy = GET_CXY( barrier_xp );
297    simple_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
298
299    // release memory allocated for barrier descriptor
300    req.type = KMEM_KCM;
301    req.ptr  = barrier_ptr;
302    kmem_remote_free( barrier_cxy , &req );
303
304#if DEBUG_BARRIER_DESTROY
305uint32_t    cycle   = (uint32_t)hal_get_cycles();
306thread_t  * this    = CURRENT_THREAD;
307process_t * process = this->process;
308if( cycle > DEBUG_BARRIER_DESTROY )
309printk("\n[%s] thread[%x,%x] deleted barrier (%x,%x) / cycle %d\n",
310__FUNCTION__, process->pid, this->trdid, barrier_ptr, barrier_cxy, cycle );
311#endif
312
313}  // end simple_barrier_destroy()
314
315/////////////////////////////////////////////
316void simple_barrier_wait( xptr_t barrier_xp )
317{
318    uint32_t  expected;
319    uint32_t  sense;
320    uint32_t  current;
321    uint32_t  arity;
322    xptr_t    root_xp;
323    xptr_t    lock_xp;
324    xptr_t    current_xp;
325    xptr_t    sense_xp;
326    xptr_t    arity_xp;
327
328    // get pointer on calling thread
329    thread_t * this = CURRENT_THREAD;
330
331    // check calling thread can yield
332    thread_assert_can_yield( this , __FUNCTION__ );
333
334    // get cluster and local pointer on remote barrier
335    simple_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
336    cxy_t              barrier_cxy = GET_CXY( barrier_xp );
337
338#if DEBUG_BARRIER_WAIT
339uint32_t cycle = (uint32_t)hal_get_cycles();
340if( cycle > DEBUG_BARRIER_WAIT )
341printk("\n[%s] thread[%x,%x] enter / barrier (%x,%x) / cycle %d\n",
342__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
343#endif
344
345    // build extended pointers on various barrier descriptor fields
346    lock_xp    = XPTR( barrier_cxy , &barrier_ptr->lock );
347    root_xp    = XPTR( barrier_cxy , &barrier_ptr->root );
348    current_xp = XPTR( barrier_cxy , &barrier_ptr->current );
349    sense_xp   = XPTR( barrier_cxy , &barrier_ptr->sense );
350    arity_xp   = XPTR( barrier_cxy , &barrier_ptr->arity );
351
352    // take busylock protecting the barrier state
353    remote_busylock_acquire( lock_xp );
354
355    // get sense and threads values from barrier descriptor
356    sense = hal_remote_l32( sense_xp );
357    arity = hal_remote_l32( arity_xp );
358
359    // compute expected value
360    if ( sense == 0 ) expected = 1;
361    else              expected = 0;
362
363    // increment current number of arrived threads / get value before increment
364    current = hal_remote_atomic_add( current_xp , 1 );
365
366    // last thread reset current, toggle sense, and activate all waiting threads
367    // other threads block, register in queue, and deschedule
368
369    if( current == (arity - 1) )                       // last thread
370    {
371        hal_remote_s32( current_xp , 0 );
372        hal_remote_s32( sense_xp , expected );
373
374        // unblock all waiting threads
375        while( xlist_is_empty( root_xp ) == false )
376        {
377            // get pointers on first waiting thread
378            xptr_t     thread_xp  = XLIST_FIRST( root_xp , thread_t , wait_list );
379            cxy_t      thread_cxy = GET_CXY( thread_xp );
380            thread_t * thread_ptr = GET_PTR( thread_xp );
381
382#if (DEBUG_BARRIER_WAIT & 1)
383trdid_t     trdid   = hal_remote_l32( XPTR( thread_cxy , &thread_ptr->trdid ) );
384process_t * process = hal_remote_lpt( XPTR( thread_cxy , &thread_ptr->process ) );
385pid_t       pid     = hal_remote_l32( XPTR( thread_cxy , &process->pid ) ); 
386if( cycle > DEBUG_BARRIER_WAIT )
387printk("\n[%s] thread[%x,%x] unblocks thread[%x,%x]\n",
388__FUNCTION__, this->process->pid, this->trdid, pid, trdid );
389#endif
390
391            // remove waiting thread from queue
392            xlist_unlink( XPTR( thread_cxy , &thread_ptr->wait_list ) );
393
394            // unblock waiting thread
395            thread_unblock( thread_xp , THREAD_BLOCKED_USERSYNC );
396        }
397
398        // release busylock protecting the barrier
399        remote_busylock_release( lock_xp );
400    }
401    else                                             // not the last thread
402    {
403
404#if (DEBUG_BARRIER_WAIT & 1)
405if( cycle > DEBUG_BARRIER_WAIT )
406printk("\n[%s] thread[%x,%x] blocks\n",
407__FUNCTION__, this->process->pid, this->trdid );
408#endif
409
410        // register calling thread in barrier waiting queue
411        xlist_add_last( root_xp , XPTR( local_cxy , &this->wait_list ) );
412
413        // block calling thread
414        thread_block( XPTR( local_cxy , this ) , THREAD_BLOCKED_USERSYNC );
415
416        // release busylock protecting the remote_barrier
417        remote_busylock_release( lock_xp );
418
419        // deschedule
420        sched_yield("blocked on barrier");
421    }
422
423#if DEBUG_BARRIER_WAIT
424cycle = (uint32_t)hal_get_cycles();
425if( cycle > DEBUG_BARRIER_WAIT )
426printk("\n[%s] thread[%x,%x] exit / barrier (%x,%x) / cycle %d\n",
427__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
428#endif
429
430}  // end simple_barrier_wait()
431
432/////////////////////////////////////////////////
433void simple_barrier_display( xptr_t  barrier_xp )
434{
435    // get cluster and local pointer on simple barrier
436    simple_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
437    cxy_t              barrier_cxy = GET_CXY( barrier_xp );
438
439    // get barrier global parameters
440    uint32_t current  = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->current ) );
441    uint32_t arity    = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->arity   ) );
442
443    printk("\n***** simple barrier : %d arrived threads on %d *****\n",
444    current, arity );
445
446}   // end simple_barrier_display()
447
448
449
450
451/////////////////////////////////////////////////////////////
452//      DQT barrier functions
453/////////////////////////////////////////////////////////////
454
455static void dqt_barrier_increment( xptr_t node_xp );
456
457#if DEBUG_BARRIER_CREATE
458void dqt_barrier_display( xptr_t  barrier_xp );
459#endif
460
461///////////////////////////////////////////////////////
462dqt_barrier_t * dqt_barrier_create( uint32_t    x_size,
463                                    uint32_t    y_size,
464                                    uint32_t    nthreads )
465{
466    dqt_barrier_t * barrier;       // local pointer on DQT barrier descriptor
467    xptr_t          barrier_xp;    // extended pointer on DQT barrier descriptor
468    uint32_t        z;             // actual DQT size == max(x_size,y_size)
469    uint32_t        levels;        // actual number of DQT levels
470    uint32_t        x;             // X coordinate in QDT mesh
471    uint32_t        y;             // Y coordinate in QDT mesh
472    uint32_t        l;             // level coordinate
473    kmem_req_t      req;           // kmem request
474
475    // compute number of DQT levels, depending on the mesh size
476    z      = (x_size > y_size) ? x_size : y_size;
477    levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5;
478
479// check x_size and y_size arguments
480assert( __FUNCTION__, (z <= 16) , "DQT mesh size larger than (16*16)\n");
481
482// check size of an array of 5 DQT nodes
483assert( __FUNCTION__, (sizeof(dqt_node_t) * 5 <= 512 ), "array of DQT nodes larger than 512 bytes\n");
484
485// check size of DQT barrier descriptor
486assert( __FUNCTION__, (sizeof(dqt_barrier_t) <= 0x4000 ), "DQT barrier descriptor larger than 4 pages\n");
487
488    // get pointer on client thread and process descriptors
489    thread_t  * this    = CURRENT_THREAD;
490    process_t * process = this->process;
491
492#if DEBUG_BARRIER_CREATE
493uint32_t   cycle = (uint32_t)hal_get_cycles();
494if( cycle > DEBUG_BARRIER_CREATE ) 
495printk("\n[%s] thread[%x,%x] enter : x_size %d / y_size %d / levels %d / cycle %d\n",
496__FUNCTION__, process->pid, this->trdid, x_size, y_size, levels, cycle );
497#endif
498
499    // get reference process cluster
500    xptr_t         ref_xp  = process->ref_xp;
501    cxy_t          ref_cxy = GET_CXY( ref_xp );
502
503    // 1. allocate 4 small pages for the DQT barrier descriptor in reference cluster
504    req.type   = KMEM_PPM;
505    req.order  = 2;                     // 4 small pages == 16 Kbytes                     
506    req.flags  = AF_ZERO | AF_KERNEL;
507    barrier    = kmem_remote_alloc( ref_cxy , &req );
508
509    if( barrier == NULL )
510    {
511        printk("\n[ERROR] in %s : cannot create DQT barrier\n", __FUNCTION__ );
512        return NULL;
513    }
514
515    // get pointers on DQT barrier descriptor in reference cluster
516    barrier_xp = XPTR( ref_cxy , barrier );
517
518    // initialize global parameters in DQT barrier descriptor
519    hal_remote_s32( XPTR( ref_cxy , &barrier->x_size   ) , x_size );
520    hal_remote_s32( XPTR( ref_cxy , &barrier->y_size   ) , x_size );
521    hal_remote_s32( XPTR( ref_cxy , &barrier->nthreads ) , nthreads );
522
523#if DEBUG_BARRIER_CREATE
524if( cycle > DEBUG_BARRIER_CREATE ) 
525printk("\n[%s] thread[%x,%x] created DQT barrier descriptor(%x,%x)\n",
526__FUNCTION__, process->pid, this->trdid, ref_cxy, barrier );
527#endif
528
529    // 2. allocate memory for an array of 5 DQT nodes 
530    //    in all existing clusters covered by the DQDT
531    //    (5 nodes per cluster <= 512 bytes per cluster)
532    //    and complete barrier descriptor initialisation.
533    for ( x = 0 ; x < x_size ; x++ )
534    {
535        for ( y = 0 ; y < y_size ; y++ )
536        {
537            cxy_t  cxy = HAL_CXY_FROM_XY( x , y );   // target cluster identifier
538            xptr_t local_array_xp;                   // xptr of nodes array in cluster cxy
539
540            // allocate memory in existing clusters only
541            if( LOCAL_CLUSTER->cluster_info[x][y] )
542            {
543                req.type  = KMEM_KCM;
544                req.order = 9;                    // 512 bytes
545                req.flags = AF_ZERO | AF_KERNEL;
546
547                void * ptr = kmem_remote_alloc( cxy , &req );
548
549                if( ptr == NULL )
550                {
551                    printk("\n[ERROR] in %s : cannot allocate DQT in cluster %x\n",
552                    __FUNCTION__, cxy );
553                    return NULL;
554                }
555       
556                // build extended pointer on local node array in cluster cxy         
557                            local_array_xp = XPTR( cxy , ptr );
558
559                // initialize the node_xp[x][y][l] array in barrier descriptor
560                for ( l = 0 ; l < levels ; l++ )
561                {
562                    xptr_t  node_xp = local_array_xp + ( l * sizeof(dqt_node_t) );
563                    hal_remote_s64( XPTR( ref_cxy , &barrier->node_xp[x][y][l] ), node_xp );
564
565#if (DEBUG_BARRIER_CREATE & 1)
566if( cycle > DEBUG_BARRIER_CREATE )
567printk(" - dqt_node_xp[%d,%d,%d] = (%x,%x) / &dqt_node_xp = %x\n",
568x , y , l , GET_CXY( node_xp ), GET_PTR( node_xp ), &barrier->node_xp[x][y][l] );
569#endif
570                } 
571            }
572            else   // register XPTR_NULL for all non-existing entries
573            {
574                for ( l = 0 ; l < levels ; l++ )
575                {
576                    hal_remote_s64( XPTR( ref_cxy , &barrier->node_xp[x][y][l] ), XPTR_NULL );
577                }
578            }
579        }  // end for y
580    }  // end for x
581
582#if DEBUG_BARRIER_CREATE
583if( cycle > DEBUG_BARRIER_CREATE ) 
584printk("\n[%s] thread[%x,%x] initialized array of pointers in DQT barrier\n",
585__FUNCTION__, process->pid, this->trdid );
586#endif
587
588    // 3. initialise all distributed DQT nodes using remote accesses
589    //    and the pointers stored in the node_xp[x][y][l] array
590    for ( x = 0 ; x < x_size ; x++ )
591    {
592        for ( y = 0 ; y < y_size ; y++ )
593        {
594            // initialize existing clusters only
595            if( LOCAL_CLUSTER->cluster_info[x][y] )
596            {
597                for ( l = 0 ; l < levels ; l++ )
598                {
599                                    xptr_t    parent_xp;
600                    xptr_t    child_xp[4];
601                    uint32_t  arity = 0;
602
603                    // get DQT node pointers
604                    xptr_t       node_xp  = hal_remote_l64( XPTR( ref_cxy,
605                                            &barrier->node_xp[x][y][l] ) );
606                    cxy_t        node_cxy = GET_CXY( node_xp );
607                    dqt_node_t * node_ptr = GET_PTR( node_xp ); 
608
609                    // compute arity and child_xp[i]
610                    if (l == 0 )                            // bottom DQT node
611                    {
612                        arity       = nthreads;
613
614                        child_xp[0] = XPTR_NULL;
615                        child_xp[1] = XPTR_NULL;
616                        child_xp[2] = XPTR_NULL;
617                        child_xp[3] = XPTR_NULL;
618                    }
619                    else                                    // not a bottom DQT node
620                    {
621                        arity = 0;
622
623                        // only few non-bottom nodes must be initialised
624                        if( ((x & ((1<<l)-1)) == 0) && ((y & ((1<<l)-1)) == 0) )
625                        {
626                            uint32_t cx[4];       // x coordinate for children
627                            uint32_t cy[4];       // y coordinate for children
628                            uint32_t i;
629
630                            // the child0 coordinates are equal to the parent coordinates
631                            // other children coordinates depend on the level value
632                            cx[0] = x;
633                            cy[0] = y;
634
635                            cx[1] = x;
636                            cy[1] = y + (1 << (l-1));
637
638                            cx[2] = x + (1 << (l-1));
639                            cy[2] = y;
640
641                            cx[3] = x + (1 << (l-1));
642                            cy[3] = y + (1 << (l-1));
643
644                            for ( i = 0 ; i < 4 ; i++ )
645                            {
646                                // child pointer is NULL if  outside the mesh
647                                if ( (cx[i] < x_size) && (cy[i] < y_size) ) 
648                                {
649                                    // get child_xp[i]
650                                    child_xp[i] = hal_remote_l64( XPTR( ref_cxy,
651                                                  &barrier->node_xp[cx[i]][cy[i]][l-1] ) );
652
653                                    // increment arity
654                                    arity++;
655                                }
656                                else
657                                {
658                                    child_xp[i] = XPTR_NULL;
659                                }
660                            }
661                        }
662                    }
663
664                    // compute parent_xp
665                    if( l == (levels - 1) )                      // root DQT node
666                    {
667                        parent_xp = XPTR_NULL;
668                    }
669                    else                                          // not the root
670                    {
671                        uint32_t px = 0;           // parent X coordinate
672                        uint32_t py = 0;           // parent Y coordinate
673                        bool_t   found = false;
674
675                        // compute macro_cluster x_min, x_max, y_min, y_max               
676                        uint32_t x_min = x & ~((1<<(l+1))-1);
677                        uint32_t x_max = x_min + (1<<(l+1));
678                        uint32_t y_min = y & ~((1<<(l+1))-1);
679                        uint32_t y_max = y_min + (1<<(l+1));
680
681                        // scan all clusters in macro-cluster[x][y][l] / take first active
682                        for( px = x_min ; px < x_max ; px++ )
683                        {
684                            for( py = y_min ; py < y_max ; py++ )
685                            {
686                                if( LOCAL_CLUSTER->cluster_info[px][py] ) found = true;
687                                if( found ) break;
688                            }
689                            if( found ) break;
690                        }
691
692                        parent_xp = hal_remote_l64( XPTR( ref_cxy ,
693                                    &barrier->node_xp[px][py][l+1] ) );
694                    }
695
696                    // initializes  the DQT node
697                    hal_remote_s32( XPTR( node_cxy , &node_ptr->arity )       , arity );   
698                    hal_remote_s32( XPTR( node_cxy , &node_ptr->current )     , 0 );   
699                    hal_remote_s32( XPTR( node_cxy , &node_ptr->sense )       , 0 );   
700                    hal_remote_s32( XPTR( node_cxy , &node_ptr->level )       , l );   
701                    hal_remote_s64( XPTR( node_cxy , &node_ptr->parent_xp )   , parent_xp );
702                    hal_remote_s64( XPTR( node_cxy , &node_ptr->child_xp[0] ) , child_xp[0] );
703                    hal_remote_s64( XPTR( node_cxy , &node_ptr->child_xp[1] ) , child_xp[1] );
704                    hal_remote_s64( XPTR( node_cxy , &node_ptr->child_xp[2] ) , child_xp[2] );
705                    hal_remote_s64( XPTR( node_cxy , &node_ptr->child_xp[3] ) , child_xp[3] );
706
707                    xlist_root_init( XPTR( node_cxy , &node_ptr->root ) );
708
709                    remote_busylock_init( XPTR( node_cxy , &node_ptr->lock ),
710                                          LOCK_BARRIER_STATE );
711                }
712            }
713        }
714    }
715
716#if DEBUG_BARRIER_CREATE
717cycle = (uint32_t)hal_get_cycles();
718if( cycle > DEBUG_BARRIER_CREATE ) 
719printk("\n[%s] thread[%x,%x] completed DQT barrier initialisation / cycle %d\n",
720__FUNCTION__, process->pid, this->trdid, cycle );
721dqt_barrier_display( barrier_xp );
722#endif
723
724    return barrier;
725
726}  // end dqt_barrier_create()
727
728///////////////////////////////////////////////
729void dqt_barrier_destroy( xptr_t   barrier_xp )
730{
731    kmem_req_t   req;                      // kmem request
732    uint32_t     x;
733    uint32_t     y;
734
735
736    // get DQT barrier descriptor cluster and local pointer
737    dqt_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
738    cxy_t           barrier_cxy = GET_CXY( barrier_xp );
739
740#if DEBUG_BARRIER_DESTROY
741thread_t * this  = CURRENT_THREAD;
742uint32_t   cycle = (uint32_t)hal_get_cycles();
743if( cycle > DEBUG_BARRIER_DESTROY ) 
744printk("\n[%s] thread[%x,%x] enter for barrier (%x,%x) / cycle %d\n",
745__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
746#endif
747
748    // get x_size and y_size global parameters
749    uint32_t x_size = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->x_size ) );
750    uint32_t y_size = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->y_size ) );
751
752    // 1. release memory allocated for the DQT nodes
753    //    in all clusters covered by the QDT mesh
754    for ( x = 0 ; x < x_size ; x++ )
755    {
756        for ( y = 0 ; y < y_size ; y++ )
757        {
758            // compute target cluster identifier
759            cxy_t   cxy = HAL_CXY_FROM_XY( x , y ); 
760
761            // existing cluster only
762            if( LOCAL_CLUSTER->cluster_info[x][y] )
763            {
764                // get local pointer on dqt_nodes array in target cluster 
765                xptr_t  buf_xp_xp = XPTR( barrier_cxy , &barrier_ptr->node_xp[x][y][0] );
766                xptr_t  buf_xp    = hal_remote_l64( buf_xp_xp );
767                void  * buf       = GET_PTR( buf_xp );
768
769assert( __FUNCTION__, (cxy == GET_CXY(buf_xp)) , "bad extended pointer on dqt_nodes array\n" );
770
771                req.type  = KMEM_KCM;
772                req.ptr   = buf;
773                kmem_remote_free( cxy , &req );
774
775#if DEBUG_BARRIER_DESTROY
776thread_t * this  = CURRENT_THREAD;
777uint32_t   cycle = (uint32_t)hal_get_cycles();
778if( cycle > DEBUG_BARRIER_DESTROY ) 
779printk("\n[%s] thread[%x,%x] released node array %x in cluster %x / cycle %d\n",
780__FUNCTION__, this->process->pid, this->trdid, buf, cxy, cycle );
781#endif
782            }
783        }
784    }
785
786    // 2. release memory allocated for barrier descriptor in ref cluster
787    req.type = KMEM_PPM;
788    req.ptr  = barrier_ptr;
789    kmem_remote_free( barrier_cxy , &req );
790
791#if DEBUG_BARRIER_DESTROY
792cycle = (uint32_t)hal_get_cycles();
793if( cycle > DEBUG_BARRIER_DESTROY ) 
794printk("\n[%s] thread[%x,%x] release barrier descriptor (%x,%x) / cycle %d\n",
795__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
796#endif
797
798}  // end dqt_barrier_destroy()
799
800////////////////////////////////////////////
801void dqt_barrier_wait( xptr_t   barrier_xp )
802{
803    thread_t * this = CURRENT_THREAD;
804
805    // check calling thread can yield
806    thread_assert_can_yield( this , __FUNCTION__ );
807
808    // get cluster and local pointer on DQT barrier descriptor
809    dqt_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
810    cxy_t           barrier_cxy = GET_CXY( barrier_xp );
811
812#if DEBUG_BARRIER_WAIT
813uint32_t cycle = (uint32_t)hal_get_cycles();
814if( cycle > DEBUG_BARRIER_WAIT )
815printk("\n[%s] thread[%x,%x] enter / barrier (%x,%x) / cycle %d\n",
816__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
817#endif
818
819    // get extended pointer on local bottom DQT node
820    uint32_t x       = HAL_X_FROM_CXY( local_cxy );
821    uint32_t y       = HAL_Y_FROM_CXY( local_cxy );
822    xptr_t   node_xp = hal_remote_l64( XPTR( barrier_cxy , &barrier_ptr->node_xp[x][y][0] ) );
823
824    // call recursive function to traverse DQT from bottom to root
825    dqt_barrier_increment( node_xp );
826
827#if DEBUG_BARRIER_WAIT
828cycle = (uint32_t)hal_get_cycles();
829if( cycle > DEBUG_BARRIER_WAIT )
830printk("\n[%s] thread[%x,%x] exit / barrier (%x,%x) / cycle %d\n",
831__FUNCTION__, this->trdid, this->process->pid, barrier_cxy, barrier_ptr, cycle );
832#endif
833
834}  // end dqt_barrier_wait()
835
836//////////////////////////////////////////////
837void dqt_barrier_display( xptr_t  barrier_xp )
838{
839    // get cluster and local pointer on DQT barrier
840    dqt_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
841    cxy_t           barrier_cxy = GET_CXY( barrier_xp );
842
843    // get barrier global parameters
844    uint32_t x_size   = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->x_size ) );
845    uint32_t y_size   = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->y_size ) );
846    uint32_t nthreads = hal_remote_l32( XPTR( barrier_cxy , &barrier_ptr->nthreads ) );
847
848    // compute size and number of DQT levels
849    uint32_t z      = (x_size > y_size) ? x_size : y_size;
850    uint32_t levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5;
851
852    printk("\n***** DQT barrier : x_size %d / y_size %d / nthreads %d / levels %d *****\n",
853    x_size, y_size, nthreads, levels );
854
855    uint32_t x , y , l;
856
857    for ( x = 0 ; x < x_size ; x++ )
858    {
859        for ( y = 0 ; y < y_size ; y++ )
860        {
861            printk(" - cluster[%d,%d]\n", x , y );
862
863            for ( l = 0 ; l < levels ; l++ )
864            {
865                // get pointers on target node
866                xptr_t       node_xp  = hal_remote_l64( XPTR( barrier_cxy ,
867                                        &barrier_ptr->node_xp[x][y][l] ) );
868                dqt_node_t * node_ptr = GET_PTR( node_xp );
869                cxy_t        node_cxy = GET_CXY( node_xp );
870
871                if( node_xp != XPTR_NULL )
872                {
873                     uint32_t level = hal_remote_l32( XPTR( node_cxy , &node_ptr->level       ));
874                     xptr_t   pa_xp = hal_remote_l32( XPTR( node_cxy , &node_ptr->parent_xp   ));
875                     xptr_t   c0_xp = hal_remote_l32( XPTR( node_cxy , &node_ptr->child_xp[0] ));
876                     xptr_t   c1_xp = hal_remote_l32( XPTR( node_cxy , &node_ptr->child_xp[1] ));
877                     xptr_t   c2_xp = hal_remote_l32( XPTR( node_cxy , &node_ptr->child_xp[2] ));
878                     xptr_t   c3_xp = hal_remote_l32( XPTR( node_cxy , &node_ptr->child_xp[3] ));
879
880                     printk("   . level %d : (%x,%x) / P(%x,%x) / C0(%x,%x)"
881                            " C1(%x,%x) / C2(%x,%x) / C3(%x,%x)\n",
882                     level, node_cxy, node_ptr, 
883                     GET_CXY(pa_xp), GET_PTR(pa_xp),
884                     GET_CXY(c0_xp), GET_PTR(c0_xp),
885                     GET_CXY(c1_xp), GET_PTR(c1_xp),
886                     GET_CXY(c2_xp), GET_PTR(c2_xp),
887                     GET_CXY(c3_xp), GET_PTR(c3_xp) );
888                }
889            }
890        }
891    }
892}   // end dqt_barrier_display()
893
894
895//////////////////////////////////////////////////////////////////////////////////////////
896// This static (recursive) function is called by the dqt_barrier_wait() function.
897// It traverses the DQT from bottom to root, and decrements the "current" variables.
898// For each traversed node, it blocks and deschedules if it is not the last expected
899//  thread. The last arrived thread reset the local node before returning.
900//////////////////////////////////////////////////////////////////////////////////////////
901static void dqt_barrier_increment( xptr_t  node_xp )
902{
903    uint32_t   expected;
904    uint32_t   sense;
905    uint32_t   arity;
906
907    thread_t * this = CURRENT_THREAD;
908
909    // get node cluster and local pointer
910    dqt_node_t * node_ptr = GET_PTR( node_xp );
911    cxy_t        node_cxy = GET_CXY( node_xp );
912
913    // build relevant extended pointers
914    xptr_t  arity_xp   = XPTR( node_cxy , &node_ptr->arity );
915    xptr_t  sense_xp   = XPTR( node_cxy , &node_ptr->sense );
916    xptr_t  current_xp = XPTR( node_cxy , &node_ptr->current );
917    xptr_t  lock_xp    = XPTR( node_cxy , &node_ptr->lock );
918    xptr_t  root_xp    = XPTR( node_cxy , &node_ptr->root );
919
920#if DEBUG_BARRIER_WAIT
921uint32_t   cycle = (uint32_t)hal_get_cycles();
922uint32_t   level = hal_remote_l32( XPTR( node_cxy, &node_ptr->level ) );
923if( cycle > DEBUG_BARRIER_WAIT )
924printk("\n[%s] thread[%x,%x] increments DQT node(%d,%d,%d) / cycle %d\n",
925__FUNCTION__ , this->process->pid, this->trdid, 
926HAL_X_FROM_CXY(node_cxy), HAL_Y_FROM_CXY(node_cxy), level );
927#endif
928
929    // get extended pointer on parent node
930    xptr_t  parent_xp  = hal_remote_l64( XPTR( node_cxy , &node_ptr->parent_xp ) );
931
932    // take busylock
933    remote_busylock_acquire( lock_xp );
934   
935    // get sense and arity values from barrier descriptor
936    sense = hal_remote_l32( sense_xp );
937    arity = hal_remote_l32( arity_xp );
938
939    // compute expected value
940    expected = (sense == 0) ? 1 : 0;
941
942    // increment current number of arrived threads / get value before increment
943    uint32_t current = hal_remote_atomic_add( current_xp , 1 );
944
945    // last arrived thread reset the local node, makes the recursive call
946    // on parent node, and reactivates all waiting thread when returning.
947    // other threads block, register in queue, and deschedule.
948
949    if ( current == (arity - 1) )                        // last thread 
950    {
951
952#if DEBUG_BARRIER_WAIT
953if( cycle > DEBUG_BARRIER_WAIT )
954printk("\n[%s] thread[%x,%x] reset DQT node(%d,%d,%d)\n",
955__FUNCTION__ , this->process->pid, this->trdid,
956HAL_X_FROM_CXY(node_cxy), HAL_Y_FROM_CXY(node_cxy), level );
957#endif
958        // reset the current node
959        hal_remote_s32( sense_xp   , expected );
960        hal_remote_s32( current_xp , 0 );
961
962        // release busylock protecting the current node
963        remote_busylock_release( lock_xp );
964
965        // recursive call on parent node when current node is not the root
966        if( parent_xp != XPTR_NULL) dqt_barrier_increment( parent_xp );
967
968        // unblock all waiting threads on this node
969        while( xlist_is_empty( root_xp ) == false )
970        {
971            // get pointers on first waiting thread
972            xptr_t     thread_xp  = XLIST_FIRST( root_xp , thread_t , wait_list );
973            cxy_t      thread_cxy = GET_CXY( thread_xp );
974            thread_t * thread_ptr = GET_PTR( thread_xp );
975
976#if (DEBUG_BARRIER_WAIT & 1)
977trdid_t     trdid   = hal_remote_l32( XPTR( thread_cxy , &thread_ptr->trdid ) );
978process_t * process = hal_remote_lpt( XPTR( thread_cxy , &thread_ptr->process ) );
979pid_t       pid     = hal_remote_l32( XPTR( thread_cxy , &process->pid ) ); 
980if( cycle > DEBUG_BARRIER_WAIT )
981printk("\n[%s] thread[%x,%x] unblock thread[%x,%x]\n",
982__FUNCTION__, this->process->pid, this->trdid, pid, trdid );
983#endif
984            // remove waiting thread from queue
985            xlist_unlink( XPTR( thread_cxy , &thread_ptr->wait_list ) );
986
987            // unblock waiting thread
988            thread_unblock( thread_xp , THREAD_BLOCKED_USERSYNC );
989        }
990    }
991    else                                               // not the last thread
992    {
993        // get extended pointer on xlist entry from thread
994        xptr_t  entry_xp = XPTR( local_cxy , &this->wait_list );
995       
996        // register calling thread in barrier waiting queue
997        xlist_add_last( root_xp , entry_xp );
998
999        // block calling thread
1000        thread_block( XPTR( local_cxy , this ) , THREAD_BLOCKED_USERSYNC );
1001
1002        // release busylock protecting the remote_barrier
1003        remote_busylock_release( lock_xp );
1004
1005#if DEBUG_BARRIER_WAIT
1006if( cycle > DEBUG_BARRIER_WAIT )
1007printk("\n[%s] thread[%x,%x] blocks on node(%d,%d,%d)\n",
1008__FUNCTION__ , this->process->pid, this->trdid,
1009HAL_X_FROM_CXY(node_cxy), HAL_Y_FROM_CXY(node_cxy), level );
1010#endif
1011        // deschedule
1012        sched_yield("blocked on barrier");
1013    }
1014
1015    return;
1016
1017} // end dqt_barrier_decrement()
1018
1019
Note: See TracBrowser for help on using the repository browser.