VirtualBox

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

Last change on this file since 29124 was 28800, checked in by vboxsync, 15 years ago

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

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