VirtualBox

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

Last change on this file since 25856 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*******************************************************************************/
53typedef 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 */
102static uint32_t volatile g_iHist = 0;
103static 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
138RTDECL(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
164RTDECL(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 */
206DECL_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 */
336DECL_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
389RTDECL(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
404RTDECL(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
419RTDECL(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
434RTDECL(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.

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