source: trunk/kernel/libk/remote_barrier.c

Last change on this file was 683, checked in by alain, 9 months ago

All modifications required to support the <tcp_chat> application
including error recovery in case of packet loss.A

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