semxroads-generic.cpp@ 46474

Last change on this file since 46474 was 44529, checked in by vboxsync, 12 years ago
header (C) fixes
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 15.7 KB

Line
1	/* $Id: semxroads-generic.cpp 44529 2013-02-04 15:54:15Z vboxsync $ */
2	/** @file
3	* IPRT Testcase - RTSemXRoads, generic implementation.
4	*/
5
6	/*
7	* Copyright (C) 2009-2010 Oracle Corporation
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.virtualbox.org. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*
17	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*/
26
27
28	/*******************************************************************************
29	* Header Files *
30	*******************************************************************************/
31	#define RTASSERT_QUIET
32	#include <iprt/semaphore.h>
33	#include "internal/iprt.h"
34
35	#include <iprt/asm.h>
36	#include <iprt/assert.h>
37	#include <iprt/err.h>
38	#include <iprt/mem.h>
39	#include <iprt/thread.h>
40
41	#include "internal/magics.h"
42
43
44	/*******************************************************************************
45	* Structures and Typedefs *
46	*******************************************************************************/
47	typedef struct RTSEMXROADSINTERNAL
48	{
49	/** Magic value (RTSEMXROADS_MAGIC). */
50	uint32_t volatile u32Magic;
51	uint32_t u32Padding; /*< alignment padding./
52	/* The state variable.
53	* All accesses are atomic and it bits are defined like this:
54	* Bits 0..14 - cNorthSouth.
55	* Bit 15 - Unused.
56	* Bits 16..31 - cEastWest.
57	* Bit 31 - fDirection; 0=NS, 1=EW.
58	* Bits 32..46 - cWaitingNS
59	* Bit 47 - Unused.
60	* Bits 48..62 - cWaitingEW
61	* Bit 63 - Unused.
62	*/
63	uint64_t volatile u64State;
64	/** Per-direction data. */
65	struct
66	{
67	/** What the north/south bound threads are blocking on when waiting for
68	* east/west traffic to stop. */
69	RTSEMEVENTMULTI hEvt;
70	/** Indicates whether the semaphore needs resetting. */
71	bool volatile fNeedReset;
72	} aDirs[2];
73	} RTSEMXROADSINTERNAL;
74
75
76	/*******************************************************************************
77	* Defined Constants And Macros *
78	*******************************************************************************/
79	#define RTSEMXROADS_CNT_BITS 15
80	#define RTSEMXROADS_CNT_MASK UINT64_C(0x00007fff)
81
82	#define RTSEMXROADS_CNT_NS_SHIFT 0
83	#define RTSEMXROADS_CNT_NS_MASK (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_NS_SHIFT)
84	#define RTSEMXROADS_CNT_EW_SHIFT 16
85	#define RTSEMXROADS_CNT_EW_MASK (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_EW_SHIFT)
86	#define RTSEMXROADS_DIR_SHIFT 31
87	#define RTSEMXROADS_DIR_MASK RT_BIT_64(RTSEMXROADS_DIR_SHIFT)
88
89	#define RTSEMXROADS_WAIT_CNT_NS_SHIFT 32
90	#define RTSEMXROADS_WAIT_CNT_NS_MASK (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_NS_SHIFT)
91	#define RTSEMXROADS_WAIT_CNT_EW_SHIFT 48
92	#define RTSEMXROADS_WAIT_CNT_EW_MASK (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_EW_SHIFT)
93
94
95	#if 0 /* debugging aid */
96	static uint32_t volatile g_iHist = 0;
97	static struct
98	{
99	void *tsc;
100	RTTHREAD hThread;
101	uint32_t line;
102	bool fDir;
103	void *u64State;
104	void *u64OldState;
105	bool fNeedResetNS;
106	bool fNeedResetEW;
107	const char *psz;
108	} g_aHist[256];
109
110	# define add_hist(ns, os, dir, what) \
111	do \
112	{ \
113	uint32_t i = (ASMAtomicIncU32(&g_iHist) - 1) % RT_ELEMENTS(g_aHist);\
114	g_aHist[i].line = __LINE__; \
115	g_aHist[i].u64OldState = (void *)(os); \
116	g_aHist[i].u64State = (void *)(ns); \
117	g_aHist[i].fDir = (dir); \
118	g_aHist[i].psz = (what); \
119	g_aHist[i].fNeedResetNS = pThis->aDirs[0].fNeedReset; \
120	g_aHist[i].fNeedResetEW = pThis->aDirs[1].fNeedReset; \
121	g_aHist[i].hThread = RTThreadSelf(); \
122	g_aHist[i].tsc = (void *)ASMReadTSC(); \
123	} while (0)
124
125	# undef DECL_FORCE_INLINE
126	# define DECL_FORCE_INLINE(type) static type
127	#else
128	# define add_hist(ns, os, dir, what) do { } while (0)
129	#endif
130
131
132	RTDECL(int) RTSemXRoadsCreate(PRTSEMXROADS phXRoads)
133	{
134	RTSEMXROADSINTERNAL pThis = (RTSEMXROADSINTERNAL )RTMemAlloc(sizeof(*pThis));
135	if (!pThis)
136	return VERR_NO_MEMORY;
137
138	int rc = RTSemEventMultiCreate(&pThis->aDirs[0].hEvt);
139	if (RT_SUCCESS(rc))
140	{
141	rc = RTSemEventMultiCreate(&pThis->aDirs[1].hEvt);
142	if (RT_SUCCESS(rc))
143	{
144	pThis->u32Magic = RTSEMXROADS_MAGIC;
145	pThis->u32Padding = 0;
146	pThis->u64State = 0;
147	pThis->aDirs[0].fNeedReset = false;
148	pThis->aDirs[1].fNeedReset = false;
149	*phXRoads = pThis;
150	return VINF_SUCCESS;
151	}
152	RTSemEventMultiDestroy(pThis->aDirs[0].hEvt);
153	}
154	return rc;
155	}
156
157
158	RTDECL(int) RTSemXRoadsDestroy(RTSEMXROADS hXRoads)
159	{
160	/*
161	* Validate input.
162	*/
163	RTSEMXROADSINTERNAL *pThis = hXRoads;
164	if (pThis == NIL_RTSEMXROADS)
165	return VINF_SUCCESS;
166	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
167	AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
168	Assert(!(ASMAtomicReadU64(&pThis->u64State) & (RTSEMXROADS_CNT_NS_MASK \| RTSEMXROADS_CNT_EW_MASK)));
169
170	/*
171	* Invalidate the object and free up the resources.
172	*/
173	AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSEMXROADS_MAGIC_DEAD, RTSEMXROADS_MAGIC), VERR_INVALID_HANDLE);
174
175	RTSEMEVENTMULTI hEvt;
176	ASMAtomicXchgHandle(&pThis->aDirs[0].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
177	int rc = RTSemEventMultiDestroy(hEvt);
178	AssertRC(rc);
179
180	ASMAtomicXchgHandle(&pThis->aDirs[1].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
181	rc = RTSemEventMultiDestroy(hEvt);
182	AssertRC(rc);
183
184	RTMemFree(pThis);
185	return VINF_SUCCESS;
186	}
187
188
189	/**
190	* Internal worker for RTSemXRoadsNSEnter and RTSemXRoadsEWEnter.
191	*
192	* @returns IPRT status code.
193	* @param pThis The semaphore instance.
194	* @param fDir The direction.
195	* @param uCountShift The shift count for getting the count.
196	* @param fCountMask The mask for getting the count.
197	* @param uWaitCountShift The shift count for getting the wait count.
198	* @param fWaitCountMask The mask for getting the wait count.
199	*/
200	DECL_FORCE_INLINE(int) rtSemXRoadsEnter(RTSEMXROADSINTERNAL *pThis, uint64_t fDir,
201	uint64_t uCountShift, uint64_t fCountMask,
202	uint64_t uWaitCountShift, uint64_t fWaitCountMask)
203	{
204	uint64_t u64OldState;
205	uint64_t u64State;
206
207	u64State = ASMAtomicReadU64(&pThis->u64State);
208	u64OldState = u64State;
209	add_hist(u64State, u64OldState, fDir, "enter");
210
211	for (;;)
212	{
213	if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
214	{
215	/* It flows in the right direction, try follow it before it changes. */
216	uint64_t c = (u64State & fCountMask) >> uCountShift;
217	c++;
218	Assert(c < 8*_1K);
219	u64State &= ~fCountMask;
220	u64State \|= c << uCountShift;
221	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
222	{
223	add_hist(u64State, u64OldState, fDir, "enter-simple");
224	break;
225	}
226	}
227	else if ((u64State & (RTSEMXROADS_CNT_NS_MASK \| RTSEMXROADS_CNT_EW_MASK)) == 0)
228	{
229	/* Wrong direction, but we're alone here and can simply try switch the direction. */
230	u64State &= ~(RTSEMXROADS_CNT_NS_MASK \| RTSEMXROADS_CNT_EW_MASK \| RTSEMXROADS_DIR_MASK);
231	u64State \|= (UINT64_C(1) << uCountShift) \| (fDir << RTSEMXROADS_DIR_SHIFT);
232	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
233	{
234	Assert(!pThis->aDirs[fDir].fNeedReset);
235	add_hist(u64State, u64OldState, fDir, "enter-switch");
236	break;
237	}
238	}
239	else
240	{
241	/* Add ourselves to the queue and wait for the direction to change. */
242	uint64_t c = (u64State & fCountMask) >> uCountShift;
243	c++;
244	Assert(c < RTSEMXROADS_CNT_MASK / 2);
245
246	uint64_t cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
247	cWait++;
248	Assert(cWait <= c);
249	Assert(cWait < RTSEMXROADS_CNT_MASK / 2);
250
251	u64State &= ~(fCountMask \| fWaitCountMask);
252	u64State \|= (c << uCountShift) \| (cWait << uWaitCountShift);
253
254	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
255	{
256	add_hist(u64State, u64OldState, fDir, "enter-wait");
257	for (uint32_t iLoop = 0; ; iLoop++)
258	{
259	int rc = RTSemEventMultiWait(pThis->aDirs[fDir].hEvt, RT_INDEFINITE_WAIT);
260	AssertRCReturn(rc, rc);
261
262	if (pThis->u32Magic != RTSEMXROADS_MAGIC)
263	return VERR_SEM_DESTROYED;
264
265	Assert(pThis->aDirs[fDir].fNeedReset);
266	u64State = ASMAtomicReadU64(&pThis->u64State);
267	add_hist(u64State, u64OldState, fDir, "enter-wakeup");
268	if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
269	break;
270	AssertMsg(iLoop < 1, ("%u\n", iLoop));
271	}
272
273	/* Decrement the wait count and maybe reset the semaphore (if we're last). */
274	for (;;)
275	{
276	u64OldState = u64State;
277
278	cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
279	Assert(cWait > 0);
280	cWait--;
281	u64State &= ~fWaitCountMask;
282	u64State \|= cWait << uWaitCountShift;
283
284	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
285	{
286	if (cWait == 0)
287	{
288	if (ASMAtomicXchgBool(&pThis->aDirs[fDir].fNeedReset, false))
289	{
290	add_hist(u64State, u64OldState, fDir, fDir ? "enter-reset-EW" : "enter-reset-NS");
291	int rc = RTSemEventMultiReset(pThis->aDirs[fDir].hEvt);
292	AssertRCReturn(rc, rc);
293	}
294	else
295	add_hist(u64State, u64OldState, fDir, "enter-dec-no-need");
296	}
297	break;
298	}
299	u64State = ASMAtomicReadU64(&pThis->u64State);
300	}
301	break;
302	}
303
304	add_hist(u64State, u64OldState, fDir, "enter-wait-failed");
305	}
306
307	if (pThis->u32Magic != RTSEMXROADS_MAGIC)
308	return VERR_SEM_DESTROYED;
309
310	ASMNopPause();
311	u64State = ASMAtomicReadU64(&pThis->u64State);
312	u64OldState = u64State;
313	}
314
315	/* got it! */
316	Assert((ASMAtomicReadU64(&pThis->u64State) & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));
317	return VINF_SUCCESS;
318	}
319
320
321	/**
322	* Internal worker for RTSemXRoadsNSLeave and RTSemXRoadsEWLeave.
323	*
324	* @returns IPRT status code.
325	* @param pThis The semaphore instance.
326	* @param fDir The direction.
327	* @param uCountShift The shift count for getting the count.
328	* @param fCountMask The mask for getting the count.
329	*/
330	DECL_FORCE_INLINE(int) rtSemXRoadsLeave(RTSEMXROADSINTERNAL *pThis, uint64_t fDir, uint64_t uCountShift, uint64_t fCountMask)
331	{
332	for (;;)
333	{
334	uint64_t u64OldState;
335	uint64_t u64State;
336	uint64_t c;
337
338	u64State = ASMAtomicReadU64(&pThis->u64State);
339	u64OldState = u64State;
340
341	/* The direction cannot change until we've left or we'll crash. */
342	Assert((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));
343
344	c = (u64State & fCountMask) >> uCountShift;
345	Assert(c > 0);
346	c--;
347
348	if ( c > 0
349	\|\| (u64State & ((RTSEMXROADS_CNT_NS_MASK \| RTSEMXROADS_CNT_EW_MASK) & ~fCountMask)) == 0)
350	{
351	/* We're not the last one across or there aren't any one waiting in the other direction. */
352	u64State &= ~fCountMask;
353	u64State \|= c << uCountShift;
354	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
355	{
356	add_hist(u64State, u64OldState, fDir, "leave-simple");
357	return VINF_SUCCESS;
358	}
359	}
360	else
361	{
362	/* Reverse the direction and signal the threads in the other direction. */
363	u64State &= ~(fCountMask \| RTSEMXROADS_DIR_MASK);
364	u64State \|= (uint64_t)!fDir << RTSEMXROADS_DIR_SHIFT;
365	if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
366	{
367	add_hist(u64State, u64OldState, fDir, fDir ? "leave-signal-NS" : "leave-signal-EW");
368	Assert(!pThis->aDirs[!fDir].fNeedReset);
369	ASMAtomicWriteBool(&pThis->aDirs[!fDir].fNeedReset, true);
370	int rc = RTSemEventMultiSignal(pThis->aDirs[!fDir].hEvt);
371	AssertRC(rc);
372	return VINF_SUCCESS;
373	}
374	}
375
376	ASMNopPause();
377	if (pThis->u32Magic != RTSEMXROADS_MAGIC)
378	return VERR_SEM_DESTROYED;
379	}
380	}
381
382
383	RTDECL(int) RTSemXRoadsNSEnter(RTSEMXROADS hXRoads)
384	{
385	/*
386	* Validate input.
387	*/
388	RTSEMXROADSINTERNAL *pThis = hXRoads;
389	if (pThis == NIL_RTSEMXROADS)
390	return VINF_SUCCESS;
391	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
392	AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
393
394	return rtSemXRoadsEnter(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK, RTSEMXROADS_WAIT_CNT_NS_SHIFT, RTSEMXROADS_WAIT_CNT_NS_MASK);
395	}
396
397
398	RTDECL(int) RTSemXRoadsNSLeave(RTSEMXROADS hXRoads)
399	{
400	/*
401	* Validate input.
402	*/
403	RTSEMXROADSINTERNAL *pThis = hXRoads;
404	if (pThis == NIL_RTSEMXROADS)
405	return VINF_SUCCESS;
406	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
407	AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
408
409	return rtSemXRoadsLeave(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK);
410	}
411
412
413	RTDECL(int) RTSemXRoadsEWEnter(RTSEMXROADS hXRoads)
414	{
415	/*
416	* Validate input.
417	*/
418	RTSEMXROADSINTERNAL *pThis = hXRoads;
419	if (pThis == NIL_RTSEMXROADS)
420	return VINF_SUCCESS;
421	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
422	AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
423
424	return rtSemXRoadsEnter(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK, RTSEMXROADS_WAIT_CNT_EW_SHIFT, RTSEMXROADS_WAIT_CNT_EW_MASK);
425	}
426
427
428	RTDECL(int) RTSemXRoadsEWLeave(RTSEMXROADS hXRoads)
429	{
430	/*
431	* Validate input.
432	*/
433	RTSEMXROADSINTERNAL *pThis = hXRoads;
434	if (pThis == NIL_RTSEMXROADS)
435	return VINF_SUCCESS;
436	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
437	AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
438
439	return rtSemXRoadsLeave(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK);
440	}
441

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

source: vbox/trunk/src/VBox/Runtime/generic/semxroads-generic.cpp@ 46474

Download in other formats: