semxroads-generic.cpp@ 26522

Last change on this file since 26522 was 25549, checked in by vboxsync, 15 years ago
semxroads-generic.cpp: bugfix - reset race (of course).
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 15.9 KB

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

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

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

Download in other formats: