Context Navigation

← Previous Revision
Next Revision →
Normal
Revision Log

remote_barrier.c

Last change on this file was 683, checked in by alain, 3 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

Rev	Line
[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]	41	xptr_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	//////////////////////////////////////////////////////////////
	81	error_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	/////////////////////////////////////////////////////
	162	void 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	//////////////////////////////////////////////////
	204	void 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	/////////////////////////////////////////////////////
	224	void 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	///////////////////////////////////////////////////////////
	249	simple_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
	280	uint32_t cycle = (uint32_t)hal_get_cycles();
	281	if( cycle > DEBUG_BARRIER_CREATE )
	282	printk("\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	////////////////////////////////////////////////
	291	void 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
	303	uint32_t cycle = (uint32_t)hal_get_cycles();
	304	thread_t * this = CURRENT_THREAD;
	305	process_t * process = this->process;
	306	if( cycle > DEBUG_BARRIER_DESTROY )
	307	printk("\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]	314	void 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]	337	uint32_t cycle = (uint32_t)hal_get_cycles();
[619]	338	if( cycle > DEBUG_BARRIER_WAIT )
	339	printk("\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)
	381	trdid_t trdid = hal_remote_l32( XPTR( thread_cxy , &thread_ptr->trdid ) );
	382	process_t * process = hal_remote_lpt( XPTR( thread_cxy , &thread_ptr->process ) );
	383	pid_t pid = hal_remote_l32( XPTR( thread_cxy , &process->pid ) );
	384	if( cycle > DEBUG_BARRIER_WAIT )
	385	printk("\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)
	403	if( cycle > DEBUG_BARRIER_WAIT )
	404	printk("\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]	422	cycle = (uint32_t)hal_get_cycles();
[619]	423	if( cycle > DEBUG_BARRIER_WAIT )
	424	printk("\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	/////////////////////////////////////////////////
	431	void 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
	453	static void dqt_barrier_increment( xptr_t node_xp );
	454
	455	#if DEBUG_BARRIER_CREATE
[635]	456	void dqt_barrier_display( xptr_t barrier_xp );
[619]	457	#endif
	458
	459	///////////////////////////////////////////////////////
	460	dqt_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]	477	assert( __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]	481	assert( __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]	485	assert( __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
	493	uint32_t cycle = (uint32_t)hal_get_cycles();
	494	if( cycle > DEBUG_BARRIER_CREATE )
	495	printk("\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
	522	if( cycle > DEBUG_BARRIER_CREATE )
[635]	523	printk("\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]	560	if( cycle > DEBUG_BARRIER_CREATE )
	561	printk(" - dqt_node_xp[%d,%d,%d] = (%x,%x) / &dqt_node_xp = %x\n",
	562	x , 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
	577	if( cycle > DEBUG_BARRIER_CREATE )
[635]	578	printk("\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
	711	cycle = (uint32_t)hal_get_cycles();
	712	if( cycle > DEBUG_BARRIER_CREATE )
	713	printk("\n[%s] thread[%x,%x] completed DQT barrier initialisation / cycle %d\n",
	714	__FUNCTION__, process->pid, this->trdid, cycle );
	715	dqt_barrier_display( barrier_xp );
	716	#endif
	717
	718	return barrier;
	719
	720	} // end dqt_barrier_create()
	721
	722	///////////////////////////////////////////////
	723	void 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]	733	thread_t * this = CURRENT_THREAD;
[619]	734	uint32_t cycle = (uint32_t)hal_get_cycles();
	735	if( cycle > DEBUG_BARRIER_DESTROY )
	736	printk("\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]	764	thread_t * this = CURRENT_THREAD;
	765	uint32_t cycle = (uint32_t)hal_get_cycles();
[619]	766	if( cycle > DEBUG_BARRIER_DESTROY )
[635]	767	printk("\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
	780	cycle = (uint32_t)hal_get_cycles();
	781	if( cycle > DEBUG_BARRIER_DESTROY )
[635]	782	printk("\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	////////////////////////////////////////////
	789	void 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
	801	uint32_t cycle = (uint32_t)hal_get_cycles();
	802	if( cycle > DEBUG_BARRIER_WAIT )
	803	printk("\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
	816	cycle = (uint32_t)hal_get_cycles();
	817	if( cycle > DEBUG_BARRIER_WAIT )
	818	printk("\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	//////////////////////////////////////////////
	825	void 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	//////////////////////////////////////////////////////////////////////////////////////////
	889	static 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
	909	uint32_t cycle = (uint32_t)hal_get_cycles();
	910	uint32_t level = hal_remote_l32( XPTR( node_cxy, &node_ptr->level ) );
	911	if( cycle > DEBUG_BARRIER_WAIT )
	912	printk("\n[%s] thread[%x,%x] increments DQT node(%d,%d,%d) / cycle %d\n",
	913	__FUNCTION__ , this->process->pid, this->trdid,
	914	HAL_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
	941	if( cycle > DEBUG_BARRIER_WAIT )
	942	printk("\n[%s] thread[%x,%x] reset DQT node(%d,%d,%d)\n",
	943	__FUNCTION__ , this->process->pid, this->trdid,
	944	HAL_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)
	965	trdid_t trdid = hal_remote_l32( XPTR( thread_cxy , &thread_ptr->trdid ) );
	966	process_t * process = hal_remote_lpt( XPTR( thread_cxy , &thread_ptr->process ) );
	967	pid_t pid = hal_remote_l32( XPTR( thread_cxy , &process->pid ) );
	968	if( cycle > DEBUG_BARRIER_WAIT )
	969	printk("\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
	994	if( cycle > DEBUG_BARRIER_WAIT )
	995	printk("\n[%s] thread[%x,%x] blocks on node(%d,%d,%d)\n",
	996	__FUNCTION__ , this->process->pid, this->trdid,
	997	HAL_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.

Context Navigation

source: trunk/kernel/libk/remote_barrier.c

Download in other formats: