Context Navigation

source: soft/giet_vm/giet_common/kernel_locks.c @ 632

Last change on this file since 632 was 632, checked in by alain, 9 years ago

Introduce two new atomic read-the-write functions, that can be used
to set or reset a bit field in a shared 32 bits word:

_atomic_or()
_atpmic_and()

File size: 18.5 KB

Rev	Line
[455]	1	///////////////////////////////////////////////////////////////////////////////////
[495]	2	// File : kernel_locks.c
[455]	3	// Date : 01/12/2014
	4	// Author : alain greiner
	5	// Copyright (c) UPMC-LIP6
	6	///////////////////////////////////////////////////////////////////////////////////
	7
[495]	8	#include "kernel_locks.h"
[455]	9	#include "giet_config.h"
[466]	10	#include "hard_config.h"
[455]	11	#include "utils.h"
[466]	12	#include "tty0.h"
	13	#include "kernel_malloc.h"
[495]	14	#include "io.h"
[455]	15
	16	///////////////////////////////////////////////////
	17	unsigned int _atomic_increment( unsigned int* ptr,
[495]	18	int increment )
[455]	19	{
	20	unsigned int value;
	21
	22	asm volatile (
	23	"1234: \n"
	24	"move $10, %1 \n" /* $10 <= ptr */
	25	"move $11, %2 \n" /* $11 <= increment */
	26	"ll $12, 0($10) \n" /* $12 <= ptr /
	27	"addu $13, $11, $12 \n" /* $13 <= ptr + increment /
[632]	28	"sc $13, 0($10) \n" /* ptr <= $12 /
[455]	29	"beqz $13, 1234b \n" /* retry if failure */
	30	"move %0, $12 \n" /* value <= ptr if success /
	31	: "=r" (value)
	32	: "r" (ptr), "r" (increment)
	33	: "$10", "$11", "$12", "$13", "memory" );
	34
	35	return value;
	36	}
	37
[632]	38	////////////////////////////////////
	39	void _atomic_or( unsigned int* ptr,
	40	unsigned int mask )
	41	{
	42	asm volatile (
	43	"1789: \n"
	44	"move $10, %0 \n" /* $10 <= ptr */
	45	"move $11, %1 \n" /* $11 <= mask */
	46	"ll $12, 0($10) \n" /* $12 <= ptr /
	47	"or $12, $11, $12 \n" /* $12 <= ptr \| mask /
	48	"sc $12, 0($10) \n" /* ptr <= $12 /
	49	"beqz $12, 1789b \n" /* retry if failure */
	50	"nop \n"
	51	:
	52	: "r" (ptr), "r" (mask)
	53	: "$10", "$11", "$12", "memory" );
	54	}
[495]	55
[632]	56	////////////////////////////////////
	57	void _atomic_and( unsigned int* ptr,
	58	unsigned int mask )
	59	{
	60	asm volatile (
	61	"1945: \n"
	62	"move $10, %0 \n" /* $10 <= ptr */
	63	"move $11, %1 \n" /* $11 <= mask */
	64	"ll $12, 0($10) \n" /* $12 <= ptr /
	65	"and $12, $11, $12 \n" /* $13 <= ptr & mask /
	66	"sc $12, 0($10) \n" /* ptr <= new /
	67	"beqz $12, 1945b \n" /* retry if failure */
	68	"nop \n"
	69	:
	70	: "r" (ptr), "r" (mask)
	71	: "$10", "$11", "$12", "memory" );
	72	}
	73
	74
[466]	75	///////////////////////////////////////////////////////////////////////////////////
	76	// Simple lock access functions
	77	///////////////////////////////////////////////////////////////////////////////////
	78
	79	////////////////////////////////////////////////
	80	void _simple_lock_acquire( simple_lock_t* lock )
[455]	81	{
[466]	82
	83	#if GIET_DEBUG_SIMPLE_LOCK
	84	unsigned int gpid = _get_procid();
	85	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	86	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	87	unsigned int l = gpid & ((1<<P_WIDTH)-1);
	88	_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] enters acquire() at cycle %d\n",
	89	x , y , l , _get_proctime() );
	90	#endif
	91
	92	asm volatile ( "1515: \n"
[495]	93	"lw $2, 0(%0) \n"
	94	"bnez $2, 1515b \n"
	95	"ll $2, 0(%0) \n"
	96	"bnez $2, 1515b \n"
	97	"li $3, 1 \n"
	98	"sc $3, 0(%0) \n"
	99	"beqz $3, 1515b \n"
[466]	100	:
	101	: "r"(lock)
	102	: "$2", "$3", "memory" );
	103
	104	#if GIET_DEBUG_SIMPLE_LOCK
	105	_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] exit acquire() at cycle %d\n",
	106	x , y , l , _get_proctime() );
	107	#endif
	108
	109	}
	110
	111	////////////////////////////////////////////////
	112	void _simple_lock_release( simple_lock_t* lock )
	113	{
[495]	114	asm volatile ( "sync" ); // for consistency
[466]	115
[495]	116	lock->value = 0;
	117
[466]	118	#if GIET_DEBUG_SIMPLE_LOCK
	119	unsigned int gpid = _get_procid();
	120	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	121	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	122	unsigned int l = gpid & ((1<<P_WIDTH)-1);
	123	_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] release() at cycle %d\n",
	124	x , y , l , _get_proctime() );
	125	#endif
	126
	127	}
	128
	129
	130	///////////////////////////////////////////////////////////////////////////////////
	131	// Queuing Lock access functions
	132	///////////////////////////////////////////////////////////////////////////////////
	133
	134	/////////////////////////////////////////
	135	void _spin_lock_init( spin_lock_t* lock )
	136	{
[455]	137	lock->current = 0;
	138	lock->free = 0;
	139
[466]	140	#if GIET_DEBUG_SPIN_LOCK
[455]	141	unsigned int gpid = _get_procid();
	142	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	143	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	144	unsigned int l = gpid & ((1<<P_WIDTH)-1);
[495]	145	_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] initializes lock %x at cycle %d\n",
	146	x, y, l, (unsigned int)lock, _get_proctime() );
[455]	147	#endif
	148
	149	}
	150
	151
[466]	152	////////////////////////////////////////////
	153	void _spin_lock_acquire( spin_lock_t* lock )
[455]	154	{
	155	// get next free slot index fromlock
	156	unsigned int ticket = _atomic_increment( &lock->free, 1 );
	157
[466]	158	#if GIET_DEBUG_SPIN_LOCK
[455]	159	unsigned int gpid = _get_procid();
	160	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	161	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	162	unsigned int l = gpid & ((1<<P_WIDTH)-1);
[495]	163	_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] get ticket %d for lock %x at cycle %d"
	164	" / current = %d / free = %d\n",
	165	x, y, l, ticket, (unsigned int)lock, _get_proctime(),
	166	lock->current, lock->free );
[455]	167	#endif
	168
	169	// poll the spin_lock current slot index
[495]	170	while ( ioread32( &lock->current ) != ticket ) asm volatile ("nop");
[455]	171
[466]	172	#if GIET_DEBUG_SPIN_LOCK
[495]	173	_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] get lock %x at cycle %d"
	174	" / current = %d / free = %d\n",
	175	x, y, l, (unsigned int)lock, _get_proctime(),
	176	lock->current, lock->free );
[455]	177	#endif
	178
	179	}
	180
[466]	181	////////////////////////////////////////////
	182	void _spin_lock_release( spin_lock_t* lock )
[455]	183	{
[495]	184	asm volatile ( "sync" ); // for consistency
[455]	185
[495]	186	lock->current = lock->current + 1;
[455]	187
[466]	188	#if GIET_DEBUG_SPIN_LOCK
[495]	189	_nolock_printf("\n[DEBUG SPIN_LOCK] P[%d,%d,%d] release lock %x at cycle %d"
	190	" / current = %d / free = %d\n",
	191	x, y, l, (unsigned int)lock, _get_proctime(),
	192	lock->current, lock->free );
[455]	193	#endif
	194
	195	}
	196
[495]	197
	198
[466]	199	///////////////////////////////////////////////////////////////////////////////////
[495]	200	// SQT lock access functions
[466]	201	///////////////////////////////////////////////////////////////////////////////////
[455]	202
[466]	203	///////////////////////////////////////////////////////////////////////////////////
[495]	204	// This recursive function is used by the _sqt_lock_init() function
	205	// to initializes the SQT nodes (mainly the parent and child pointers).
	206	// It traverses the SQT from top to bottom.
	207	// The SQT can be uncomplete (when xmax or ymax are not power of 2),
	208	// and the recursion stops when the (x,y) coordinates exceed the footprint.
[466]	209	///////////////////////////////////////////////////////////////////////////////////
[495]	210	static
	211	void _sqt_lock_build( sqt_lock_t* lock, // pointer on the SQT lock
	212	unsigned int x, // node X coordinate
	213	unsigned int y, // node Y coordinate
	214	unsigned int level, // node level
	215	sqt_lock_node_t* parent, // pointer on parent node
	216	unsigned int xmax, // SQT X size
	217	unsigned int ymax ) // SQT Y size
[466]	218	{
[455]	219
[495]	220	#if GIET_DEBUG_SQT_LOCK
[466]	221	unsigned int gpid = _get_procid();
	222	unsigned int px = gpid >> (Y_WIDTH + P_WIDTH);
	223	unsigned int py = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	224	unsigned int pl = gpid & ((1<<P_WIDTH)-1);
	225	#endif
[455]	226
[466]	227	// get target node pointer
[495]	228	sqt_lock_node_t* node = lock->node[x][y][level];
[466]	229
	230	if (level == 0 ) // terminal case
	231	{
	232	// initializes target node
[495]	233	node->current = 0;
	234	node->free = 0;
	235	node->level = 0;
[466]	236	node->parent = parent;
[495]	237	node->child[0] = NULL;
	238	node->child[1] = NULL;
	239	node->child[2] = NULL;
	240	node->child[3] = NULL;
[455]	241
[495]	242	#if GIET_DEBUG_SQT_LOCK
	243	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
	244	" parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
	245	px , py , pl , x , y , level ,
	246	(unsigned int)node->parent ,
	247	(unsigned int)node->child[0] ,
	248	(unsigned int)node->child[1] ,
	249	(unsigned int)node->child[2] ,
	250	(unsigned int)node->child[3] );
[466]	251	#endif
[455]	252
[466]	253	}
	254	else // non terminal case
	255	{
[495]	256	unsigned int cx[4]; // x coordinate for children
	257	unsigned int cy[4]; // y coordinate for children
	258	unsigned int i; // child index
[455]	259
[466]	260	// the child0 coordinates are equal to the parent coordinates
[495]	261	// other childs coordinates are incremented depending on the level value
	262	cx[0] = x;
	263	cy[0] = y;
	264
	265	cx[1] = x + (1 << (level-1));
	266	cy[1] = y;
	267
	268	cx[2] = x;
	269	cy[2] = y + (1 << (level-1));
	270
	271	cx[3] = x + (1 << (level-1));
	272	cy[3] = y + (1 << (level-1));
	273
	274	// initializes target node
	275	for ( i = 0 ; i < 4 ; i++ )
[466]	276	{
[495]	277	if ( (cx[i] < xmax) && (cy[i] < ymax) )
	278	node->child[i] = lock->node[cx[i]][cy[i]][level-1];
	279	else
	280	node->child[i] = NULL;
[466]	281	}
[495]	282	node->current = 0;
	283	node->free = 0;
[466]	284	node->level = level;
	285	node->parent = parent;
	286
[495]	287	#if GIET_DEBUG_SQT_LOCK
	288	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
	289	" parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
[466]	290	px , py , pl , x , y , level ,
[495]	291	(unsigned int)node->parent ,
	292	(unsigned int)node->child[0] ,
	293	(unsigned int)node->child[1] ,
	294	(unsigned int)node->child[2] ,
	295	(unsigned int)node->child[3] );
[466]	296	#endif
	297
[495]	298	// recursive calls for children nodes
	299	for ( i = 0 ; i < 4 ; i++ )
	300	{
	301	if ( (cx[i] < xmax) && (cy[i] < ymax) )
	302	_sqt_lock_build( lock,
	303	cx[i],
	304	cy[i],
	305	level-1,
	306	node,
	307	xmax,
	308	ymax );
	309	}
[466]	310	}
[495]	311	} // end _sqt_lock_build()
[466]	312
	313	/////////////////////////////////////////////////////////////////////////////////
[495]	314	// This external function initialises the distributed SQT lock.
	315	// It allocates memory for the distributed SQT nodes in clusters,
	316	// and initializes the SQT nodes pointers array (stored in cluster[0][0].
	317	// The SQT can be "uncomplete" as SQT lock nodes are only build in clusters
	318	// containing processors.
	319	// The actual number of SQT locks nodes in a cluster[x][y] depends on (x,y):
	320	// At least 1 node / at most 5 nodes per cluster:
	321	// - lock arbitrating between all processors of 1 cluster has level 0,
	322	// - lock arbitrating between all processors of 4 clusters has level 1,
	323	// - lock arbitrating between all processors of 16 clusters has level 2,
	324	// - lock arbitrating between all processors of 64 clusters has level 3,
	325	// - lock arbitrating between all processors of 256 clusters has level 4,
[466]	326	/////////////////////////////////////////////////////////////////////////////////
[495]	327	void _sqt_lock_init( sqt_lock_t* lock )
[466]	328	{
[495]	329	unsigned int levels;
	330	unsigned int xmax;
	331	unsigned int ymax;
[466]	332
[495]	333	// compute the smallest SQT covering all processors
	334	_get_sqt_footprint( &xmax, &ymax, &levels );
[466]	335
	336
[495]	337	#if GIET_DEBUG_SQT_LOCK
[466]	338	unsigned int gpid = _get_procid();
	339	unsigned int px = gpid >> (Y_WIDTH + P_WIDTH);
	340	unsigned int py = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	341	unsigned int pl = gpid & ((1<<P_WIDTH)-1);
[495]	342	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] initialises SQT lock %x : \n"
	343	" xmax = %d / ymax = %d / levels = %d\n",
	344	px , py , pl , (unsigned int)lock ,
	345	xmax , ymax , levels );
[466]	346	#endif
	347
[495]	348
	349	unsigned int x; // x coordinate for one SQT node
	350	unsigned int y; // y coordinate for one SQT node
	351	unsigned int l; // level for one SQT node
	352
	353	for ( x = 0 ; x < xmax ; x++ )
[466]	354	{
[495]	355	for ( y = 0 ; y < ymax ; y++ )
[466]	356	{
	357	for ( l = 0 ; l < levels ; l++ ) // level 0 nodes
	358	{
	359
	360	if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) \|\|
[495]	361	( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) \|\|
	362	( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) \|\|
	363	( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) \|\|
	364	( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
[466]	365	{
[495]	366	lock->node[x][y][l] =
	367	(sqt_lock_node_t*)_remote_malloc( sizeof(sqt_lock_node_t),
	368	x, y );
[466]	369
[495]	370	#if GIET_DEBUG_SQT_LOCK
	371	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] allocates SQT node[%d,%d,%d]"
	372	" : vaddr = %x\n",
[466]	373	px , py , pl , x , y , l , (unsigned int)lock->node[x][y][l] );
	374	#endif
	375	}
	376	}
	377	}
	378	}
	379
[495]	380	// recursively initialize all SQT nodes from root to bottom
	381	_sqt_lock_build( lock, // pointer on the SQT lock descriptor
[466]	382	0, // x coordinate
	383	0, // y coordinate
[495]	384	levels-1, // level in SQT
	385	NULL, // pointer on the parent node
	386	xmax, // SQT footprint X size
	387	ymax ); // SQT footprint X size
[466]	388
	389	asm volatile ("sync" ::: "memory");
	390
[495]	391	#if GIET_DEBUG_SQT_LOCK
	392	_nolock_printf("\n[DEBUG SQT_LOCK] SQT nodes initialisation completed\n");
[466]	393	#endif
	394
[495]	395	} // end _sqt_lock_init()
[466]	396
	397	//////////////////////////////////////////////////////////////////////////////////
[495]	398	// This recursive function is used by the sqt_lock_acquire() function to get
	399	// a distributed SQT lock: It tries to get each local queuing lock on the path
	400	// from bottom to top, and starting from bottom.
	401	// It is blocking : it polls each "partial lock until it can be taken.
	402	// The lock is finally obtained when all locks, at all levels are taken.
	403	//////////////////////////////////////////////////////////////////////////////////
	404	static
	405	void _sqt_lock_take( sqt_lock_node_t* node )
	406	{
	407	// get next free ticket from local lock
	408	unsigned int ticket = _atomic_increment( &node->free, 1 );
	409
	410	#if GIET_DEBUG_SQT_LOCK
	411	unsigned int gpid = _get_procid();
	412	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	413	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	414	unsigned int l = gpid & ((1<<P_WIDTH)-1);
	415	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] get ticket %d for SQT lock %x"
	416	" / level = %d / current = %d / free = %d\n",
	417	x , y , l , ticket , (unsigned int)node ,
	418	node->level , node->current , node->free );
	419	#endif
	420
	421	// poll the local lock current index
	422	while ( ioread32( &node->current ) != ticket ) asm volatile( "nop" );
	423
	424	#if GIET_DEBUG_SQT_LOCK
	425	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] get SQT lock %x"
	426	" / level = %d / current = %d / free = %d\n",
	427	x , y , l , (unsigned int)node ,
	428	node->level , node->current , node->free );
	429	#endif
	430
	431	// try to take the parent node lock until top is reached
	432	if ( node->parent != NULL ) _sqt_lock_take( node->parent );
	433
	434	} // end _sqt_lock_take()
	435
	436	//////////////////////////////////////////////////////////////////////////////////
	437	// This external function get thes SQT lock.
[466]	438	// Returns only when the lock has been taken.
	439	/////////////////////////////////////////////////////////////////////////////////
[495]	440	void _sqt_lock_acquire( sqt_lock_t* lock )
[466]	441	{
	442	// get cluster coordinates
	443	unsigned int gpid = _get_procid();
	444	unsigned int x = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<<X_WIDTH)-1);
	445	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	446
[495]	447	// try to recursively take the distributed locks (from bottom to top)
	448	_sqt_lock_take( lock->node[x][y][0] );
[455]	449	}
	450
[466]	451
	452	/////////////////////////////////////////////////////////////////////////////////
[495]	453	// This recursive function is used by the sqt_lock_release() function to
	454	// release distributed SQT lock: It releases all local locks on the path from
	455	// bottom to top, using a normal read/write, and starting from bottom.
[466]	456	/////////////////////////////////////////////////////////////////////////////////
[495]	457	static
	458	void _sqt_lock_give( sqt_lock_node_t* node )
[455]	459	{
[495]	460	// release the local lock
	461	node->current = node->current + 1;
	462
	463	#if GIET_DEBUG_SQT_LOCK
	464	unsigned int gpid = _get_procid();
	465	unsigned int x = gpid >> (Y_WIDTH + P_WIDTH);
	466	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	467	unsigned int l = gpid & ((1<<P_WIDTH)-1);
	468	_nolock_printf("\n[DEBUG SQT_LOCK] P[%d,%d,%d] release SQT lock %x"
	469	" / level = %d / current = %d / free = %d\n",
	470	x , y , l , (unsigned int)node,
	471	node->level , node->current , node->free );
	472	#endif
	473
	474	// reset parent node until top is reached
	475	if ( node->parent != NULL ) _sqt_lock_give( node->parent );
	476
	477	} // end _sqt_lock_give()
	478
	479
	480	/////////////////////////////////////////////////////////////////////////////////
	481	// This external function releases the SQT lock.
	482	/////////////////////////////////////////////////////////////////////////////////
	483	void _sqt_lock_release( sqt_lock_t* lock )
	484	{
	485	asm volatile ( "sync" ); // for consistency
	486
[466]	487	// get cluster coordinates
	488	unsigned int gpid = _get_procid();
	489	unsigned int x = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<<X_WIDTH)-1);
	490	unsigned int y = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
	491
[495]	492	// recursively reset the distributed locks (from bottom to top)
	493	_sqt_lock_give( lock->node[x][y][0] );
[455]	494	}
	495
	496	// Local Variables:
	497	// tab-width: 4
	498	// c-basic-offset: 4
	499	// c-file-offsets:((innamespace . 0)(inline-open . 0))
	500	// indent-tabs-mode: nil
	501	// End:
	502	// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
	503

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

Download in other formats: