Adding upstream version 6.1.22-dfsg.upstream/6.1.22-dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 441 insertions, 0 deletions

diff --git a/src/VBox/Runtime/generic/semxroads-generic.cpp b/src/VBox/Runtime/generic/semxroads-generic.cpp
new file mode 100644
index 00000000..aa7bcd2b
--- /dev/null
+++ b/src/VBox/Runtime/generic/semxroads-generic.cpp
@@ -0,0 +1,441 @@
+/* $Id: semxroads-generic.cpp $ */
+/** @file
+ * IPRT Testcase - RTSemXRoads, generic implementation.
+ */
+
+/*
+ * Copyright (C) 2009-2020 Oracle Corporation
+ *
+ * This file is part of VirtualBox Open Source Edition (OSE), as
+ * available from http://www.virtualbox.org. This file is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU
+ * General Public License (GPL) as published by the Free Software
+ * Foundation, in version 2 as it comes in the "COPYING" file of the
+ * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
+ * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+
+/*********************************************************************************************************************************
+*   Header Files                                                                                                                 *
+*********************************************************************************************************************************/
+#define RTASSERT_QUIET
+#include <iprt/semaphore.h>
+#include "internal/iprt.h"
+
+#include <iprt/asm.h>
+#include <iprt/assert.h>
+#include <iprt/err.h>
+#include <iprt/mem.h>
+#include <iprt/thread.h>
+
+#include "internal/magics.h"
+
+
+/*********************************************************************************************************************************
+*   Structures and Typedefs                                                                                                      *
+*********************************************************************************************************************************/
+typedef struct RTSEMXROADSINTERNAL
+{
+    /** Magic value (RTSEMXROADS_MAGIC).  */
+    uint32_t volatile   u32Magic;
+    uint32_t            u32Padding; /**< alignment padding.*/
+    /* The state variable.
+     * All accesses are atomic and it bits are defined like this:
+     *      Bits 0..14  - cNorthSouth.
+     *      Bit 15      - Unused.
+     *      Bits 16..31 - cEastWest.
+     *      Bit 31      - fDirection; 0=NS, 1=EW.
+     *      Bits 32..46 - cWaitingNS
+     *      Bit 47      - Unused.
+     *      Bits 48..62 - cWaitingEW
+     *      Bit 63      - Unused.
+     */
+    uint64_t volatile   u64State;
+    /** Per-direction data. */
+    struct
+    {
+        /** What the north/south bound threads are blocking on when waiting for
+         * east/west traffic to stop. */
+        RTSEMEVENTMULTI     hEvt;
+        /** Indicates whether the semaphore needs resetting. */
+        bool volatile       fNeedReset;
+    } aDirs[2];
+} RTSEMXROADSINTERNAL;
+
+
+/*********************************************************************************************************************************
+*   Defined Constants And Macros                                                                                                 *
+*********************************************************************************************************************************/
+#define RTSEMXROADS_CNT_BITS            15
+#define RTSEMXROADS_CNT_MASK            UINT64_C(0x00007fff)
+
+#define RTSEMXROADS_CNT_NS_SHIFT        0
+#define RTSEMXROADS_CNT_NS_MASK         (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_NS_SHIFT)
+#define RTSEMXROADS_CNT_EW_SHIFT        16
+#define RTSEMXROADS_CNT_EW_MASK         (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_EW_SHIFT)
+#define RTSEMXROADS_DIR_SHIFT           31
+#define RTSEMXROADS_DIR_MASK            RT_BIT_64(RTSEMXROADS_DIR_SHIFT)
+
+#define RTSEMXROADS_WAIT_CNT_NS_SHIFT   32
+#define RTSEMXROADS_WAIT_CNT_NS_MASK    (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_NS_SHIFT)
+#define RTSEMXROADS_WAIT_CNT_EW_SHIFT   48
+#define RTSEMXROADS_WAIT_CNT_EW_MASK    (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_EW_SHIFT)
+
+
+#if 0 /* debugging aid */
+static uint32_t volatile g_iHist = 0;
+static struct
+{
+    void *tsc;
+    RTTHREAD hThread;
+    uint32_t line;
+    bool fDir;
+    void *u64State;
+    void *u64OldState;
+    bool fNeedResetNS;
+    bool fNeedResetEW;
+    const char *psz;
+} g_aHist[256];
+
+# define add_hist(ns, os, dir, what)  \
+    do \
+    { \
+        uint32_t i = (ASMAtomicIncU32(&g_iHist) - 1) % RT_ELEMENTS(g_aHist);\
+        g_aHist[i].line         = __LINE__; \
+        g_aHist[i].u64OldState  = (void *)(os); \
+        g_aHist[i].u64State     = (void *)(ns); \
+        g_aHist[i].fDir         = (dir); \
+        g_aHist[i].psz          = (what); \
+        g_aHist[i].fNeedResetNS = pThis->aDirs[0].fNeedReset; \
+        g_aHist[i].fNeedResetEW = pThis->aDirs[1].fNeedReset; \
+        g_aHist[i].hThread      = RTThreadSelf(); \
+        g_aHist[i].tsc          = (void *)ASMReadTSC(); \
+    } while (0)
+
+# undef DECL_FORCE_INLINE
+# define DECL_FORCE_INLINE(type) static type
+#else
+# define add_hist(ns, os, dir, what)  do { } while (0)
+#endif
+
+
+RTDECL(int) RTSemXRoadsCreate(PRTSEMXROADS phXRoads)
+{
+    RTSEMXROADSINTERNAL *pThis = (RTSEMXROADSINTERNAL *)RTMemAlloc(sizeof(*pThis));
+    if (!pThis)
+        return VERR_NO_MEMORY;
+
+    int rc = RTSemEventMultiCreate(&pThis->aDirs[0].hEvt);
+    if (RT_SUCCESS(rc))
+    {
+        rc = RTSemEventMultiCreate(&pThis->aDirs[1].hEvt);
+        if (RT_SUCCESS(rc))
+        {
+            pThis->u32Magic            = RTSEMXROADS_MAGIC;
+            pThis->u32Padding          = 0;
+            pThis->u64State            = 0;
+            pThis->aDirs[0].fNeedReset = false;
+            pThis->aDirs[1].fNeedReset = false;
+            *phXRoads = pThis;
+            return VINF_SUCCESS;
+        }
+        RTSemEventMultiDestroy(pThis->aDirs[0].hEvt);
+    }
+    return rc;
+}
+
+
+RTDECL(int) RTSemXRoadsDestroy(RTSEMXROADS hXRoads)
+{
+    /*
+     * Validate input.
+     */
+    RTSEMXROADSINTERNAL *pThis = hXRoads;
+    if (pThis == NIL_RTSEMXROADS)
+        return VINF_SUCCESS;
+    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
+    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
+    Assert(!(ASMAtomicReadU64(&pThis->u64State) & (RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK)));
+
+    /*
+     * Invalidate the object and free up the resources.
+     */
+    AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSEMXROADS_MAGIC_DEAD, RTSEMXROADS_MAGIC), VERR_INVALID_HANDLE);
+
+    RTSEMEVENTMULTI hEvt;
+    ASMAtomicXchgHandle(&pThis->aDirs[0].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
+    int rc = RTSemEventMultiDestroy(hEvt);
+    AssertRC(rc);
+
+    ASMAtomicXchgHandle(&pThis->aDirs[1].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
+    rc = RTSemEventMultiDestroy(hEvt);
+    AssertRC(rc);
+
+    RTMemFree(pThis);
+    return VINF_SUCCESS;
+}
+
+
+/**
+ * Internal worker for RTSemXRoadsNSEnter and RTSemXRoadsEWEnter.
+ *
+ * @returns IPRT status code.
+ * @param   pThis               The semaphore instance.
+ * @param   fDir                The direction.
+ * @param   uCountShift         The shift count for getting the count.
+ * @param   fCountMask          The mask for getting the count.
+ * @param   uWaitCountShift     The shift count for getting the wait count.
+ * @param   fWaitCountMask      The mask for getting the wait count.
+ */
+DECL_FORCE_INLINE(int) rtSemXRoadsEnter(RTSEMXROADSINTERNAL *pThis, uint64_t fDir,
+                                        uint64_t uCountShift, uint64_t fCountMask,
+                                        uint64_t uWaitCountShift, uint64_t fWaitCountMask)
+{
+    uint64_t    u64OldState;
+    uint64_t    u64State;
+
+    u64State = ASMAtomicReadU64(&pThis->u64State);
+    u64OldState = u64State;
+    add_hist(u64State, u64OldState, fDir, "enter");
+
+    for (;;)
+    {
+        if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
+        {
+            /* It flows in the right direction, try follow it before it changes. */
+            uint64_t c = (u64State & fCountMask) >> uCountShift;
+            c++;
+            Assert(c < 8*_1K);
+            u64State &= ~fCountMask;
+            u64State |= c << uCountShift;
+            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+            {
+                add_hist(u64State, u64OldState, fDir, "enter-simple");
+                break;
+            }
+        }
+        else if ((u64State & (RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK)) == 0)
+        {
+            /* Wrong direction, but we're alone here and can simply try switch the direction. */
+            u64State &= ~(RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK | RTSEMXROADS_DIR_MASK);
+            u64State |= (UINT64_C(1) << uCountShift) | (fDir << RTSEMXROADS_DIR_SHIFT);
+            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+            {
+                Assert(!pThis->aDirs[fDir].fNeedReset);
+                add_hist(u64State, u64OldState, fDir, "enter-switch");
+                break;
+            }
+        }
+        else
+        {
+            /* Add ourselves to the queue and wait for the direction to change. */
+            uint64_t c = (u64State & fCountMask) >> uCountShift;
+            c++;
+            Assert(c < RTSEMXROADS_CNT_MASK / 2);
+
+            uint64_t cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
+            cWait++;
+            Assert(cWait <= c);
+            Assert(cWait < RTSEMXROADS_CNT_MASK / 2);
+
+            u64State &= ~(fCountMask | fWaitCountMask);
+            u64State |= (c << uCountShift) | (cWait << uWaitCountShift);
+
+            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+            {
+                add_hist(u64State, u64OldState, fDir, "enter-wait");
+                for (uint32_t iLoop = 0; ; iLoop++)
+                {
+                    int rc = RTSemEventMultiWait(pThis->aDirs[fDir].hEvt, RT_INDEFINITE_WAIT);
+                    AssertRCReturn(rc, rc);
+
+                    if (pThis->u32Magic != RTSEMXROADS_MAGIC)
+                        return VERR_SEM_DESTROYED;
+
+                    Assert(pThis->aDirs[fDir].fNeedReset);
+                    u64State = ASMAtomicReadU64(&pThis->u64State);
+                    add_hist(u64State, u64OldState, fDir, "enter-wakeup");
+                    if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
+                        break;
+                    AssertMsg(iLoop < 1, ("%u\n", iLoop));
+                }
+
+                /* Decrement the wait count and maybe reset the semaphore (if we're last). */
+                for (;;)
+                {
+                    u64OldState = u64State;
+
+                    cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
+                    Assert(cWait > 0);
+                    cWait--;
+                    u64State &= ~fWaitCountMask;
+                    u64State |= cWait << uWaitCountShift;
+
+                    if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+                    {
+                        if (cWait == 0)
+                        {
+                            if (ASMAtomicXchgBool(&pThis->aDirs[fDir].fNeedReset, false))
+                            {
+                                add_hist(u64State, u64OldState, fDir, fDir ? "enter-reset-EW" : "enter-reset-NS");
+                                int rc = RTSemEventMultiReset(pThis->aDirs[fDir].hEvt);
+                                AssertRCReturn(rc, rc);
+                            }
+                            else
+                                add_hist(u64State, u64OldState, fDir, "enter-dec-no-need");
+                        }
+                        break;
+                    }
+                    u64State = ASMAtomicReadU64(&pThis->u64State);
+                }
+                break;
+            }
+
+            add_hist(u64State, u64OldState, fDir, "enter-wait-failed");
+        }
+
+        if (pThis->u32Magic != RTSEMXROADS_MAGIC)
+            return VERR_SEM_DESTROYED;
+
+        ASMNopPause();
+        u64State = ASMAtomicReadU64(&pThis->u64State);
+        u64OldState = u64State;
+    }
+
+    /* got it! */
+    Assert((ASMAtomicReadU64(&pThis->u64State) & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));
+    return VINF_SUCCESS;
+}
+
+
+/**
+ * Internal worker for RTSemXRoadsNSLeave and RTSemXRoadsEWLeave.
+ *
+ * @returns IPRT status code.
+ * @param   pThis               The semaphore instance.
+ * @param   fDir                The direction.
+ * @param   uCountShift         The shift count for getting the count.
+ * @param   fCountMask          The mask for getting the count.
+ */
+DECL_FORCE_INLINE(int) rtSemXRoadsLeave(RTSEMXROADSINTERNAL *pThis, uint64_t fDir, uint64_t uCountShift, uint64_t fCountMask)
+{
+    for (;;)
+    {
+        uint64_t u64OldState;
+        uint64_t u64State;
+        uint64_t c;
+
+        u64State = ASMAtomicReadU64(&pThis->u64State);
+        u64OldState = u64State;
+
+        /* The direction cannot change until we've left or we'll crash. */
+        Assert((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));
+
+        c = (u64State & fCountMask) >> uCountShift;
+        Assert(c > 0);
+        c--;
+
+        if (    c > 0
+            ||  (u64State & ((RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK) & ~fCountMask)) == 0)
+        {
+            /* We're not the last one across or there aren't any one waiting in the other direction.  */
+            u64State &= ~fCountMask;
+            u64State |= c << uCountShift;
+            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+            {
+                add_hist(u64State, u64OldState, fDir, "leave-simple");
+                return VINF_SUCCESS;
+            }
+        }
+        else
+        {
+            /* Reverse the direction and signal the threads in the other direction. */
+            u64State &= ~(fCountMask | RTSEMXROADS_DIR_MASK);
+            u64State |= (uint64_t)!fDir << RTSEMXROADS_DIR_SHIFT;
+            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
+            {
+                add_hist(u64State, u64OldState, fDir, fDir ? "leave-signal-NS" : "leave-signal-EW");
+                Assert(!pThis->aDirs[!fDir].fNeedReset);
+                ASMAtomicWriteBool(&pThis->aDirs[!fDir].fNeedReset, true);
+                int rc = RTSemEventMultiSignal(pThis->aDirs[!fDir].hEvt);
+                AssertRC(rc);
+                return VINF_SUCCESS;
+            }
+        }
+
+        ASMNopPause();
+        if (pThis->u32Magic != RTSEMXROADS_MAGIC)
+            return VERR_SEM_DESTROYED;
+    }
+}
+
+
+RTDECL(int) RTSemXRoadsNSEnter(RTSEMXROADS hXRoads)
+{
+    /*
+     * Validate input.
+     */
+    RTSEMXROADSINTERNAL *pThis = hXRoads;
+    if (pThis == NIL_RTSEMXROADS)
+        return VINF_SUCCESS;
+    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
+    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
+
+    return rtSemXRoadsEnter(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK, RTSEMXROADS_WAIT_CNT_NS_SHIFT, RTSEMXROADS_WAIT_CNT_NS_MASK);
+}
+
+
+RTDECL(int) RTSemXRoadsNSLeave(RTSEMXROADS hXRoads)
+{
+    /*
+     * Validate input.
+     */
+    RTSEMXROADSINTERNAL *pThis = hXRoads;
+    if (pThis == NIL_RTSEMXROADS)
+        return VINF_SUCCESS;
+    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
+    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
+
+    return rtSemXRoadsLeave(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK);
+}
+
+
+RTDECL(int) RTSemXRoadsEWEnter(RTSEMXROADS hXRoads)
+{
+    /*
+     * Validate input.
+     */
+    RTSEMXROADSINTERNAL *pThis = hXRoads;
+    if (pThis == NIL_RTSEMXROADS)
+        return VINF_SUCCESS;
+    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
+    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
+
+    return rtSemXRoadsEnter(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK, RTSEMXROADS_WAIT_CNT_EW_SHIFT, RTSEMXROADS_WAIT_CNT_EW_MASK);
+}
+
+
+RTDECL(int) RTSemXRoadsEWLeave(RTSEMXROADS hXRoads)
+{
+    /*
+     * Validate input.
+     */
+    RTSEMXROADSINTERNAL *pThis = hXRoads;
+    if (pThis == NIL_RTSEMXROADS)
+        return VINF_SUCCESS;
+    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
+    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
+
+    return rtSemXRoadsLeave(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK);
+}
+