Context Navigation

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

Last change on this file since 680 was 671, checked in by alain, 4 years ago
Cosmetic.
File size: 38.5 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: