source: trunk/kernel/libk/remote_barrier.c

Last change on this file was 683, checked in by alain, 6 years ago

All modifications required to support the <tcp_chat> application
including error recovery in case of packet loss.A
File size: 38.3 KB
Line 
1/*
2 * remote_barrier.c - POSIX barrier implementation.
3 *
4 * Author Alain Greiner (2016,2017,2018,2019,2020)
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 impl barrier descriptor
87
88 // get pointer on local process_descriptor
89 process_t * process = CURRENT_THREAD->process;
90
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 );
95
96 // allocate memory for generic barrier descriptor
97 gen_barrier_ptr = kmem_remote_alloc( ref_cxy,
98 bits_log2(sizeof(generic_barrier_t)),
99 AF_KERNEL );
100 if( gen_barrier_ptr == NULL )
101 {
102 printk("\n[ERROR] in %s : cannot create generic barrier\n", __FUNCTION__ );
103 return -1;
104 }
105
106 // create implementation specific barrier descriptor
107 if( attr == NULL ) // simple barrier
108 {
109 // create simple barrier descriptor
110 barrier = simple_barrier_create( count );
111 }
112 else // QDT barrier
113 {
114 uint32_t x_size = attr->x_size;
115 uint32_t y_size = attr->y_size;
116 uint32_t nthreads = attr->nthreads;
117
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 );
123 kmem_remote_free( ref_cxy,
124 gen_barrier_ptr,
125 bits_log2(sizeof(generic_barrier_t)) );
126 return -1;
127 }
128
129 // create DQT barrier descriptor
130 barrier = dqt_barrier_create( x_size , y_size , nthreads );
131 }
132
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;
140 }
141
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
148 xptr_t root_xp = XPTR( ref_cxy , &ref_ptr->barrier_root );
149 xptr_t lock_xp = XPTR( ref_cxy , &ref_ptr->sync_lock );
150 xptr_t entry_xp = XPTR( ref_cxy , &gen_barrier_ptr->list );
151
152 // register barrier in reference process xlist of barriers
153 remote_busylock_acquire( lock_xp );
154 xlist_add_first( root_xp , entry_xp );
155 remote_busylock_release( lock_xp );
156
157 return 0;
158
159} // en generic_barrier_create()
160
161/////////////////////////////////////////////////////
162void generic_barrier_destroy( xptr_t gen_barrier_xp )
163{
164 // get pointer on local process_descriptor
165 process_t * process = CURRENT_THREAD->process;
166
167 // get pointers on reference process
168 xptr_t ref_xp = process->ref_xp;
169 cxy_t ref_cxy = GET_CXY( ref_xp );
170 process_t * ref_ptr = GET_PTR( ref_xp );
171
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
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)) );
200
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
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 );
229
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 ) );
233
234 // buil extended pointer on the implementation specific barrier descriptor
235 xptr_t barrier_xp = XPTR( gen_barrier_cxy , extend );
236
237 // display barrier state
238 if( is_dqt ) dqt_barrier_display( barrier_xp );
239 else simple_barrier_display( barrier_xp );
240}
241
242
243
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
262 barrier = kmem_remote_alloc( ref_cxy,
263 bits_log2(sizeof(simple_barrier_t)),
264 AF_ZERO );
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 // get barrier cluster and local pointer
294 cxy_t barrier_cxy = GET_CXY( barrier_xp );
295 simple_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
296
297 // release memory allocated for barrier descriptor
298 kmem_remote_free( barrier_cxy,
299 barrier_ptr,
300 bits_log2(sizeof(simple_barrier_t)) );
301
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
313/////////////////////////////////////////////
314void simple_barrier_wait( xptr_t barrier_xp )
315{
316 uint32_t expected;
317 uint32_t sense;
318 uint32_t current;
319 uint32_t arity;
320 xptr_t root_xp;
321 xptr_t lock_xp;
322 xptr_t current_xp;
323 xptr_t sense_xp;
324 xptr_t arity_xp;
325
326 // get pointer on calling thread
327 thread_t * this = CURRENT_THREAD;
328
329 // check calling thread can yield
330 thread_assert_can_yield( this , __FUNCTION__ );
331
332 // get cluster and local pointer on remote barrier
333 simple_barrier_t * barrier_ptr = GET_PTR( barrier_xp );
334 cxy_t barrier_cxy = GET_CXY( barrier_xp );
335
336#if DEBUG_BARRIER_WAIT
337uint32_t cycle = (uint32_t)hal_get_cycles();
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 );
341#endif
342
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 );
349
350 // take busylock protecting the barrier state
351 remote_busylock_acquire( lock_xp );
352
353 // get sense and threads values from barrier descriptor
354 sense = hal_remote_l32( sense_xp );
355 arity = hal_remote_l32( arity_xp );
356
357 // compute expected value
358 if ( sense == 0 ) expected = 1;
359 else expected = 0;
360
361 // increment current number of arrived threads / get value before increment
362 current = hal_remote_atomic_add( current_xp , 1 );
363
364 // last thread reset current, toggle sense, and activate all waiting threads
365 // other threads block, register in queue, and deschedule
366
367 if( current == (arity - 1) ) // last thread
368 {
369 hal_remote_s32( current_xp , 0 );
370 hal_remote_s32( sense_xp , expected );
371
372 // unblock all waiting threads
373 while( xlist_is_empty( root_xp ) == false )
374 {
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 );
379
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 );
387#endif
388
389 // remove waiting thread from queue
390 xlist_unlink( XPTR( thread_cxy , &thread_ptr->wait_list ) );
391
392 // unblock waiting thread
393 thread_unblock( thread_xp , THREAD_BLOCKED_USERSYNC );
394 }
395
396 // release busylock protecting the barrier
397 remote_busylock_release( lock_xp );
398 }
399 else // not the last thread
400 {
401
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 );
406#endif
407
408 // register calling thread in barrier waiting queue
409 xlist_add_last( root_xp , XPTR( local_cxy , &this->wait_list ) );
410
411 // block calling thread
412 thread_block( XPTR( local_cxy , this ) , THREAD_BLOCKED_USERSYNC );
413
414 // release busylock protecting the remote_barrier
415 remote_busylock_release( lock_xp );
416
417 // deschedule
418 sched_yield("blocked on barrier");
419 }
420
421#if DEBUG_BARRIER_WAIT
422cycle = (uint32_t)hal_get_cycles();
423if( cycle > DEBUG_BARRIER_WAIT )
424printk("\n[%s] thread[%x,%x] exit / barrier (%x,%x) / cycle %d\n",
425__FUNCTION__, this->process->pid, this->trdid, barrier_cxy, barrier_ptr, cycle );
426#endif
427
428} // end simple_barrier_wait()
429
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 );
436
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
449/////////////////////////////////////////////////////////////
450// DQT barrier functions
451/////////////////////////////////////////////////////////////
452
453static void dqt_barrier_increment( xptr_t node_xp );
454
455#if DEBUG_BARRIER_CREATE
456void dqt_barrier_display( xptr_t barrier_xp );
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
472 // compute number of DQT levels, depending on the mesh size
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
477assert( __FUNCTION__, (z <= 16),
478"DQT mesh size larger than (16*16)\n");
479
480// check size of an array of 5 DQT nodes
481assert( __FUNCTION__, (sizeof(dqt_node_t) * 5 <= 512 ),
482"array of DQT nodes larger than 512 bytes\n");
483
484// check size of DQT barrier descriptor
485assert( __FUNCTION__, (sizeof(dqt_barrier_t) <= 0x4000 ),
486"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 barrier = kmem_remote_alloc( ref_cxy,
505 CONFIG_PPM_PAGE_ORDER + 2, // 4 small pages
506 AF_ZERO );
507 if( barrier == NULL )
508 {
509 printk("\n[ERROR] in %s : cannot create DQT barrier\n", __FUNCTION__ );
510 return NULL;
511 }
512
513 // get pointers on DQT barrier descriptor in reference cluster
514 barrier_xp = XPTR( ref_cxy , barrier );
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 )
523printk("\n[%s] thread[%x,%x] created DQT barrier descriptor(%x,%x)\n",
524__FUNCTION__, process->pid, this->trdid, ref_cxy, barrier );
525#endif
526
527 // 2. allocate memory for an array of 5 DQT nodes
528 // in all existing clusters covered by the DQDT
529 // (5 nodes per cluster <= 512 bytes per cluster)
530 // and complete barrier descriptor initialisation.
531 for ( x = 0 ; x < x_size ; x++ )
532 {
533 for ( y = 0 ; y < y_size ; y++ )
534 {
535 cxy_t cxy = HAL_CXY_FROM_XY( x , y ); // target cluster identifier
536 xptr_t local_array_xp; // xptr on nodes array in cluster cxy
537
538 // allocate memory in existing clusters only
539 if( LOCAL_CLUSTER->cluster_info[x][y] )
540 {
541 void * ptr = kmem_remote_alloc( cxy , 9 , AF_ZERO ); // 512 bytes
542
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 );
552
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 );
558
559#if (DEBUG_BARRIER_CREATE & 1)
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
564 }
565 }
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
575
576#if DEBUG_BARRIER_CREATE
577if( cycle > DEBUG_BARRIER_CREATE )
578printk("\n[%s] thread[%x,%x] initialized array of pointers in DQT barrier\n",
579__FUNCTION__, process->pid, this->trdid );
580#endif
581
582 // 3. initialise all distributed DQT nodes using remote accesses
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{
725 uint32_t x;
726 uint32_t y;
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
733thread_t * this = CURRENT_THREAD;
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
744 // 1. release memory allocated for the DQT nodes
745 // in all clusters covered by the QDT mesh
746 for ( x = 0 ; x < x_size ; x++ )
747 {
748 for ( y = 0 ; y < y_size ; y++ )
749 {
750 // compute target cluster identifier
751 cxy_t cxy = HAL_CXY_FROM_XY( x , y );
752
753 // existing cluster only
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
761 kmem_remote_free( cxy , buf , 9 ); // 512 bytes
762
763#if DEBUG_BARRIER_DESTROY
764thread_t * this = CURRENT_THREAD;
765uint32_t cycle = (uint32_t)hal_get_cycles();
766if( cycle > DEBUG_BARRIER_DESTROY )
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 );
769#endif
770 }
771 }
772 }
773
774 // 2. release memory allocated for barrier descriptor in ref cluster
775 kmem_remote_free( barrier_cxy,
776 barrier_ptr,
777 CONFIG_PPM_PAGE_ORDER + 2 ); // 4 small pages
778
779#if DEBUG_BARRIER_DESTROY
780cycle = (uint32_t)hal_get_cycles();
781if( cycle > DEBUG_BARRIER_DESTROY )
782printk("\n[%s] thread[%x,%x] release barrier descriptor (%x,%x) / cycle %d\n",
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
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 );
830
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 ) );
835
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;
839
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
868 printk(" . level %d : (%x,%x) / P(%x,%x) / C0(%x,%x)"
869 " C1(%x,%x) / C2(%x,%x) / C3(%x,%x)\n",
870 level, node_cxy, node_ptr,
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
883//////////////////////////////////////////////////////////////////////////////////////////
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.
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.