VirtualBox

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

Last change on this file since 37043 was 33540, checked in by vboxsync, 14 years ago

*: spelling fixes, thanks Timeless!
  • 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 33540 2010-10-28 09:27:05Z vboxsync $ */
2/** @file
3 * IPRT Testcase - RTSemXRoads, generic implementation.
4 */
5
6/*
7 * Copyright (C) 2009 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*******************************************************************************/
47typedef 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 */
96static uint32_t volatile g_iHist = 0;
97static 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
132RTDECL(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
158RTDECL(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 */
200DECL_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 */
330DECL_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
383RTDECL(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
398RTDECL(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
413RTDECL(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
428RTDECL(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.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette